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.
Arytmetyka modularna
- 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
Arytmetyka modularna
Ł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.
\(\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.