Witam
Mam problem z rozwiązaniem tego zadania
\(\displaystyle{ 2000x=3(mod 643)}\)
proszę o pomoc
Kongruencja mod 643
- JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
Kongruencja mod 643
\(\displaystyle{ 643}\) jest liczbą pierwszą, więc \(\displaystyle{ \mathbb{Z}_{643}}\) jest ciałem. Wystarczy znaleźć element odwrotny do \(\displaystyle{ 2000}\), tj. taki, że \(\displaystyle{ 2000 \cdot n = 1}\) w tym ciele (przy tej kongruencji).
Zauważmy, że \(\displaystyle{ 2000 \equiv 71 \pmod{643}}\). Stąd:
\(\displaystyle{ 2000x\equiv 71x \pmod{643} \Rightarrow 71\cdot(1+18) x\equiv 63x\pmod{643}}\)
Widzimy, że dodanie \(\displaystyle{ 18\cdot 71}\) jest równoważne odjęciu \(\displaystyle{ 8}\) w tym ciele. Zatem:
\(\displaystyle{ 2000x\equiv 71x \pmod{643} \Rightarrow 71\cdot(1 + 18\cdot 9)x\equiv 643x \equiv -x \pmod{643}}\)
Zatem, skoro \(\displaystyle{ 1 + 18\cdot 9 \equiv 163 \pmod{643}}\):
\(\displaystyle{ 71x\equiv 3\pmod{643}\\71x \cdot 163 \equiv 3\cdot 163\pmod{643}\\ -x \equiv 489 \pmod{643} \\ x \equiv 154 \pmod{643}}\)
Zauważmy, że \(\displaystyle{ 2000 \equiv 71 \pmod{643}}\). Stąd:
\(\displaystyle{ 2000x\equiv 71x \pmod{643} \Rightarrow 71\cdot(1+18) x\equiv 63x\pmod{643}}\)
Widzimy, że dodanie \(\displaystyle{ 18\cdot 71}\) jest równoważne odjęciu \(\displaystyle{ 8}\) w tym ciele. Zatem:
\(\displaystyle{ 2000x\equiv 71x \pmod{643} \Rightarrow 71\cdot(1 + 18\cdot 9)x\equiv 643x \equiv -x \pmod{643}}\)
Zatem, skoro \(\displaystyle{ 1 + 18\cdot 9 \equiv 163 \pmod{643}}\):
\(\displaystyle{ 71x\equiv 3\pmod{643}\\71x \cdot 163 \equiv 3\cdot 163\pmod{643}\\ -x \equiv 489 \pmod{643} \\ x \equiv 154 \pmod{643}}\)