Arytmetyka modularna

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
soljack
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 8 wrz 2014, o 10:18
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

Arytmetyka modularna

Post autor: soljack »

Mam znaleźć najmniejsze takie x, że:
\(\displaystyle{ 17 * x = 1}\) (mod 39)

No więc skorzystałem z Tw. Eulera i wyszło że:
\(\displaystyle{ 17^{36} = 1}\) (mod 39)

Tyle że nie wiem jak to zminimalizować bo x musi być najmniejsze.

Proszę o pomoc.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Arytmetyka modularna

Post autor: Premislav »

Łatwiej zapewne byłoby to osiągnąć, stosując algorytm Euklidesa:
\(\displaystyle{ 39=2 \cdot 17+5\\
17=3 \cdot 5+2\\
5=2 \cdot 2+1}\)

Zatem \(\displaystyle{ 1=5-2 \cdot 2=39-2 \cdot 17-2 \cdot (17-3 \cdot 5)=39-4 \cdot 17+6(39-2 \cdot 17)=7 \cdot 39-16 \cdot 17}\). Stąd znajdujemy element odwrotny do \(\displaystyle{ 17}\) w pierścieniu reszt z dzielenia przez \(\displaystyle{ 39}\) (będzie równy \(\displaystyle{ 23}\), a znajdujemy go, szukając takiego \(\displaystyle{ p=-16+39k}\), że \(\displaystyle{ p \in {0,1,...38}}\), \(\displaystyle{ k \in \mathbb{Z}}\)), mnożymy przezeń kongruencję stronami, redukujemy modulo \(\displaystyle{ 39}\), jeśli coś się da i voila.
ODPOWIEDZ