Dwie ostatnie cyfry - kongurencja

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
andrzej1976
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 16 paź 2012, o 22:15
Płeć: Mężczyzna
Lokalizacja: Tomaszowo

Dwie ostatnie cyfry - kongurencja

Post autor: andrzej1976 »

Mam pytanie odnosnie nastepujacego przykladu (nalezy znalesc 2 ostatnie cyfry) :
\(\displaystyle{ 203 ^{228}-1234 \equiv x (mod 100)\\
203 \equiv 3 (mod 100)\\
203 ^{228} \equiv 3^{228} (mod 100)\\}\)

Skorzystalem z twierdzenia Eulera gdyz NWD(3, 100) = 1
Z funkcji Eulera uzyskalem 40, f(100) = 40
a nastepnie przeksztalcilem:
\(\displaystyle{ 3^{228} = (3^{40})^{5}*3^{28} \\

3^{40} \equiv 1 (mod 100) \\
(3^{40})^{5} \equiv 1^{5} (mod 100) \\
3^{7} \equiv -13 (mod 100) \\
(3^{7})^{4} \equiv (-13)^{4} (mod 100) \\
(3^{7})^{4} \equiv 28561 \\

1234 \equiv 34}\)

tak więc:
\(\displaystyle{ 203 ^{228}-1234 \equiv 28561-34 (mod 100) \\
203 ^{228}-1234 \equiv 28527 (mod 100) \\}\)

Odp. Dwie ostatnie cyfry to 2 i 7.
Czy moje rozumowanie jest prawidlowe? Jesli nie to prosze o naprowadzenie na prawidlowy tor.
ODPOWIEDZ