tw eulera

[Forte]

ma nadzieje, że nie utracilem sprawnosci rachunkowej

Zadanie:
wyznacz resztę z dzielenia \(\displaystyle{ 13^{141}}\) przez \(\displaystyle{ 32}\)

otóż z tw Eulera \(\displaystyle{ 13^{\phi(32)}\equiv 1 \mod 32}\)

\(\displaystyle{ \phi(2^5)=2^5-2^4=32-16=16}\)

\(\displaystyle{ 13^{16}\equiv 1 \mod 32}\)

Prowadzę rachunki

\(\displaystyle{ 13^{141}=\left1(3^{16}\right)^8\cdot 13^{13}\equiv 13^{13}}\)

\(\displaystyle{ x\equiv 13^{13}}\)
stąd

\(\displaystyle{ 13^3 x \equiv 13^{16}\equiv 1 \mod 32}\)

\(\displaystyle{ 169\cdot 13 x \equiv 1 \mod 32}\)

\(\displaystyle{ 9\cdot 13 x \equiv 1 \mod 32}\)

\(\displaystyle{ 117 x \equiv 1 \mod 32}\)

\(\displaystyle{ 21 x \equiv 1 \mod 32}\)

\(\displaystyle{ x=29}\)

odp: \(\displaystyle{ 13^{141}\equiv 29 \mod 32}\)

[Vax]

Dobrze, ale da się szybciej. Z funkcji Carmichaela otrzymujemy \(\displaystyle{ 13^{\lambda(32)} \equiv 1\pmod{32} \iff 13^{8} \equiv 1\pmod{32}/^{17} \Rightarrow \\ 13^{136} \equiv 1\pmod{32} /\cdot 13^5 \Leftrightarrow 13^{141} \equiv 13^5 \equiv 13\cdot 169^2 \equiv 13\cdot 9^2 \equiv 13\cdot 17 \equiv 29\pmod{32}}\)