przystawanie

[gelo]

Pokazać, że \(a ^{m} \equiv a ^{m-\varphi(m)}\) \(mod\) \(m\).

[gpl1260]

Trzeba pokazać że m dzieli liczbę \(a ^{m-\varphi(m)}(a ^{\varphi(m)}-1)\). Niech \(m=MA\) gdzie \(A=NWD(m,a)\) oraz \(M=\frac{m}{A}\perp a\). Oczywiście A dzieli a, i w konsekwencji \(A\mid a ^{m-\varphi(m)}\). Na mocy tw. Eulera-Fermata, M dzieli \(a ^{\varphi(M)}-1\), i ponieważ \(\varphi\) jest multiplikatywna, to M dzieli \(a ^{\varphi(m)}-1\), co kończy dowód.