Proszę o pomoc z następującym zadaniem:
Rozwiąż kongruencję \(\displaystyle{ 119x + 31 = 191x mod 625.}\)
Czy mógłby je ktoś rozpisać krok po kroku?
rozwiąż kongruencję
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
rozwiąż kongruencję
W taki sposób się niczego nie nauczysz i potem przyjdziesz na forum z takim samym zadaniem, tylko z innymi danymi liczbowymi. Ale to Twój wybór.
Równoważnie \(\displaystyle{ 72 x \equiv 31\pmod{625}}\) (po prostu przeniosłem \(\displaystyle{ 119x}\) na drugą stronę). Dalej należy znaleźć element odwrotny do \(\displaystyle{ 72}\) względem mnożenia nodulo
\(\displaystyle{ 625}\), tj. znaleźć takie \(\displaystyle{ s\in \ZZ}\) (oczywiście nie są one jedyne), że
\(\displaystyle{ 72s+625t=1}\) dla pewnego \(\displaystyle{ t \in \ZZ}\). A do tego można użyć algorytmu Euklidesa:
\(\displaystyle{ 625=8\cdot 72+49\\ 72=1\cdot49+23\\49=2\cdot 23+3\\23=7\cdot 3+2\\3=1\cdot 2+1}\)
A zatem zaczynając od drugiej strony i przechodząc coraz wyżej z podstawieniami, mamy
\(\displaystyle{ 1=3-1\cdot 2=(49-2\cdot 23)-(23-7\cdot 3)=\\=(625-8\cdot 72-2\cdot (72-49))-(72-49-7\cdot(49-2\cdot 23))=11\cdot 625-105\cdot 72+14\cdot 49=25\cdot 625-217\cdot 72}\). Czyli naszym s może być \(\displaystyle{ -217}\), a jak chcemy liczbę z zakresu \(\displaystyle{ \left\{ 0,...624\right\}}\) (oczywiście bez krotności piątki, bo to dzielniki zera), to bierzemy \(\displaystyle{ -217+625=408}\).
Zatem \(\displaystyle{ 72 x \equiv 31\pmod{625}}\) mnożymy stronami przez \(\displaystyle{ 408}\) (z powyższych obliczeń wynika \(\displaystyle{ 408\cdot 72\equiv 1\pmod{625}}\)) i mamy
\(\displaystyle{ x\equiv 408 \cdot 31\pmod{625}}\). Na kalkulatorze możemy jeszcze sprawdzić, że \(\displaystyle{ 408\cdot 31=20\cdot 625+148}\) (ja to policzyłem w pamięci, ale nie ma takiej potrzeby) i możemy ostatecznie zapisać: \(\displaystyle{ x\equiv 148 \pmod{625}}\) - to jest rozwiązanie (wszystkie \(\displaystyle{ x}\) całkowite spełniające taką zależność są rozwiązaniami).
Jeżeli nie wiesz, dlaczego robimy tak, a nie inaczej, to poczytaj sobie o rozszerzonym algorytmie Euklidesa.
Równoważnie \(\displaystyle{ 72 x \equiv 31\pmod{625}}\) (po prostu przeniosłem \(\displaystyle{ 119x}\) na drugą stronę). Dalej należy znaleźć element odwrotny do \(\displaystyle{ 72}\) względem mnożenia nodulo
\(\displaystyle{ 625}\), tj. znaleźć takie \(\displaystyle{ s\in \ZZ}\) (oczywiście nie są one jedyne), że
\(\displaystyle{ 72s+625t=1}\) dla pewnego \(\displaystyle{ t \in \ZZ}\). A do tego można użyć algorytmu Euklidesa:
\(\displaystyle{ 625=8\cdot 72+49\\ 72=1\cdot49+23\\49=2\cdot 23+3\\23=7\cdot 3+2\\3=1\cdot 2+1}\)
A zatem zaczynając od drugiej strony i przechodząc coraz wyżej z podstawieniami, mamy
\(\displaystyle{ 1=3-1\cdot 2=(49-2\cdot 23)-(23-7\cdot 3)=\\=(625-8\cdot 72-2\cdot (72-49))-(72-49-7\cdot(49-2\cdot 23))=11\cdot 625-105\cdot 72+14\cdot 49=25\cdot 625-217\cdot 72}\). Czyli naszym s może być \(\displaystyle{ -217}\), a jak chcemy liczbę z zakresu \(\displaystyle{ \left\{ 0,...624\right\}}\) (oczywiście bez krotności piątki, bo to dzielniki zera), to bierzemy \(\displaystyle{ -217+625=408}\).
Zatem \(\displaystyle{ 72 x \equiv 31\pmod{625}}\) mnożymy stronami przez \(\displaystyle{ 408}\) (z powyższych obliczeń wynika \(\displaystyle{ 408\cdot 72\equiv 1\pmod{625}}\)) i mamy
\(\displaystyle{ x\equiv 408 \cdot 31\pmod{625}}\). Na kalkulatorze możemy jeszcze sprawdzić, że \(\displaystyle{ 408\cdot 31=20\cdot 625+148}\) (ja to policzyłem w pamięci, ale nie ma takiej potrzeby) i możemy ostatecznie zapisać: \(\displaystyle{ x\equiv 148 \pmod{625}}\) - to jest rozwiązanie (wszystkie \(\displaystyle{ x}\) całkowite spełniające taką zależność są rozwiązaniami).
Jeżeli nie wiesz, dlaczego robimy tak, a nie inaczej, to poczytaj sobie o rozszerzonym algorytmie Euklidesa.