Witam mam problem z takimi przykładami nie wiem co zrobić jeśli NWD(x,y) jest różne od 1.
1)
2^144 mod 8
2^144 mod 216
2)
3^144 mod 27
3^144 mod 216
Z góry dzięki!
Funkcja Eulera przykłady.
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
- Jerry
- Expert
- Posty: 3536
- Rejestracja: 18 maja 2009, 09:23
- Podziękowania: 51 razy
- Otrzymane podziękowania: 1940 razy
Re: Funkcja Eulera przykłady.
Na piechotę:
1)
1)
- \(2^{144}=2^{141}\cdot8+0\equiv 0\mod8\\\)
-
\(2^{144}=256^{18}=(216+40)^{18}\equiv 40^{18}\mod216\\
40^{18}=1600^9=(7\cdot216+88)^9\equiv 88^9\mod 216\\
88^9=681472^3=(3155\cdot216-8)^3\equiv(-8)^3\mod216\\
(-8)^3=-521=-3\cdot216+136\equiv 136\mod216\)
Ostatecznie:
\(2^{144}\equiv 136\mod216\)
- \(3^{144}=3^{141}\cdot27+0\equiv 0\mod27\\\)
-
\(3^{144}=729^{24}=(3\cdot216+81)^{24}\equiv 81^{24}\mod216\\
81^{24}=729^4=(3\cdot216+81)^4\equiv 81^4\mod 216\\
81^4=6561^2=(30\cdot216+81)^2\equiv81^2\mod216\\
81^2=6561=30\cdot216+81\equiv 81\mod216\)
Ostatecznie:
\(3^{144}\equiv 81\mod216\)