Kongruencja mod 643

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Paragon16
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 23 paź 2011, o 22:46
Płeć: Mężczyzna
Lokalizacja: Warszawa

Kongruencja mod 643

Post autor: Paragon16 »

Witam
Mam problem z rozwiązaniem tego zadania
\(\displaystyle{ 2000x=3(mod 643)}\)
proszę o pomoc
Awatar użytkownika
JakimPL
Użytkownik
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

Post autor: JakimPL »

\(\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}}\)
ODPOWIEDZ