Rozwiązać kongruencje

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
ebasse
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 6 sty 2011, o 21:23
Płeć: Mężczyzna
Lokalizacja: Skała
Podziękował: 1 raz

Rozwiązać kongruencje

Post autor: ebasse » 24 sie 2011, o 12:29

Witam, mam problem w rozwiązaniu układu kongruencji.
Proszę o pomoc, ewentualne wskazówki. Cokolwiek co naprowadzi i pomoże to zrozumieć. Z góry dziekuję

\(\displaystyle{ 5x\equiv3\pmod{11} \\ 6x\equiv4\pmod{34}}\)
Ostatnio zmieniony 24 sie 2011, o 12:31 przez ares41, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Proszę zapoznać się z pkt. 2.7.1 instrukcji LaTeX-u.

soulman64
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 23 sie 2011, o 23:09
Płeć: Mężczyzna
Lokalizacja: Płock

Rozwiązać kongruencje

Post autor: soulman64 » 24 sie 2011, o 14:04

\(\displaystyle{ x \in (0,11\rangle}\), bo jest modulo \(\displaystyle{ 11}\) czyli zawiera sie do \(\displaystyle{ 11}\) włacznie
\(\displaystyle{ 5 \cdot 1=5}\) modulo \(\displaystyle{ 11}\) przystaje do \(\displaystyle{ 3}\)
\(\displaystyle{ 5 \cdot 2=10}\) reszta \(\displaystyle{ 1}\)
\(\displaystyle{ 5 \cdot 3=15\ \ \ \frac{15}{11}}\) daje reszte \(\displaystyle{ 3}\)
\(\displaystyle{ 5 \cdot 4=20}\) reszta z dzielenia przez \(\displaystyle{ 11\text{ to } 8}\)

\(\displaystyle{ 5 \cdot 5=25 \text{ reszta to } 3 \\ 5 \cdot 6=30 \text{ reszta } 8 \\ 5 \cdot 7=35 \text{ reszta } 2 \\ 5 \cdot 8=40 \text{ reszta } 7 \\ 5 \cdot 9=45 \text{ reszta } 1 \\ 5 \cdot 10=50 \text{ reszta } 6 \\ 5 \cdot 11=55 \text{ reszta } 0}\)

czyli \(\displaystyle{ 5x}\)przystaje do \(\displaystyle{ 3\pmod{11}}\) tylko w trzech przypadkach gdy \(\displaystyle{ x=3 \vee x=5 \vee x=1}\)

teraz wystarczy sprawdzić z \(\displaystyle{ \pmod{34}}\) tez cyfry

\(\displaystyle{ 6 \cdot 3=24 \pmod {34} \text{ to będzie } 10\\ 6 \cdot 1=6 \pmod {34} \text{ to będzie } 28\\ 6 \cdot 5=30 \text{ czyli przystaje do }4}\)

Odp. \(\displaystyle{ x=5}\)
Ostatnio zmieniony 24 sie 2011, o 14:10 przez ares41, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Rozwiązać kongruencje

Post autor: » 24 sie 2011, o 14:59

Oczywiście powyższe rozwiązanie jest błędne - można robić w ten sposób, czyli na piechotę, ale pod warunkiem, że nie robi się tylu błędów merytorycznych i rachunkowych.

Na piechotę - sprawdzamy ręcznie, że rozwiązaniem pierwszej kongruencji w zbiorze \(\displaystyle{ \{0,1,\ldots ,10\}}\) jest tylko \(\displaystyle{ 5}\), więc wiemy, że \(\displaystyle{ x=11k+5}\). Wstawiając to drugiej kongruencji dostajemy kolejno:
\(\displaystyle{ 6(11k+5)\equiv4\pmod{34}\\ 66k\equiv -26\pmod{34}\\ 33k\equiv -13\pmod{17}\\ -k\equiv -13\pmod{17}\\ k\equiv 13\pmod{17}}\)
czyli \(\displaystyle{ k=17l+13}\), czyli:
\(\displaystyle{ x=11(17l+13)+5=187l+148}\)
więc jedynym rozwiązaniem w przedziale \(\displaystyle{ [0, 11cdot 17)}\) jest \(\displaystyle{ x=148}\)

Nie na piechotę można tak - zaczynamy od podzielenia drugiej kongruencji stronami przez dwa:
\(\displaystyle{ \begin{cases}5x\equiv3\pmod{11} \\ 3x\equiv2\pmod{17}\end{cases}}\)
Znajdujemy teraz odwrotność piątki modulo \(\displaystyle{ 11}\) i odwrotność trójki modulo \(\displaystyle{ 17}\), tzn. takie liczby \(\displaystyle{ a,b}\), że \(\displaystyle{ 5a\equiv 1\pmod{11}, 3b\equiv 1\pmod{17}}\) (można to zrobić przy użyciu rozszerzonego algorytmu Euklidesa lub "zgadując"). Są to \(\displaystyle{ a=9,b=6}\). Mnożymy więć pierwszą kongruencję przez \(\displaystyle{ 9}\), a drugą przez \(\displaystyle{ 6}\):
\(\displaystyle{ \begin{cases}x\equiv5\pmod{11} \\ x\equiv12\pmod{17}\end{cases}}\)
Teraz znajdujemy rozwiązania kongruencji:
\(\displaystyle{ \begin{cases}x_1\equiv1\pmod{11} \\ x_1\equiv0\pmod{17}\end{cases}}\)
\(\displaystyle{ \begin{cases}x_2\equiv0\pmod{11} \\ x_2\equiv1\pmod{17}\end{cases}}\)
W pierwszym przypadku \(\displaystyle{ x_1=17k}\), czyli \(\displaystyle{ 17k\equiv1\pmod{11}}\), czyli \(\displaystyle{ 6k\equiv1\pmod{11}}\), czyli \(\displaystyle{ k=2}\), czyli \(\displaystyle{ x_1=34}\)
W drugim wypadku \(\displaystyle{ x_2=11k}\), czyli \(\displaystyle{ 11k\equiv1\pmod{17}}\), czyli \(\displaystyle{ k=14}\), czyli \(\displaystyle{ x_2=154}\)
Na końcu obliczamy
\(\displaystyle{ x=5x_1+12x_2\mod (11\cdot 17)= 148}\)

Q.

ebasse
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 6 sty 2011, o 21:23
Płeć: Mężczyzna
Lokalizacja: Skała
Podziękował: 1 raz

Rozwiązać kongruencje

Post autor: ebasse » 24 sie 2011, o 15:23

Qń pisze: Na piechotę - sprawdzamy ręcznie, że rozwiązaniem pierwszej kongruencji w zbiorze \(\displaystyle{ \{0,1,\ldots ,10\}}\) jest tylko \(\displaystyle{ 5}\), więc wiemy, że \(\displaystyle{ x=11k+5}\). Wstawiając to drugiej kongruencji dostajemy kolejno:
\(\displaystyle{ 6(11k+5)\equiv4\pmod{34}\\ 66k\equiv -26\pmod{34}\\ 33k\equiv -13\pmod{17}\\ -k\equiv -13\pmod{17}\\ k\equiv 13\pmod{17}}\)
czyli \(\displaystyle{ k=17l+13}\), czyli:
\(\displaystyle{ x=11(17l+13)+5=187l+148}\)
więc jedynym rozwiązaniem w przedziale \(\displaystyle{ [0, 11cdot 17)}\) jest \(\displaystyle{ x=148}\)
Czy mógłbyś to tak po kolei wytłumaczyć, skąd biorą się poszczególne linijki?

Np.
\(\displaystyle{ x=11k+5 \\ k\equiv 13\pmod{17} \\ -k\equiv -13\pmod{17}\\}\)

ODPOWIEDZ