Funkcja Eulera przykłady.

[Tomaszak]

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!

[Jerry]

Na piechotę:
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\)

2)

• \(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\)

Pozdrawiam