How to Prove a^m ≡ a^{m-φ(m)} mod m?

[oszust001]

How to proof that equation?
a^m \equiv a^{m-\phi(m)} mod m ?

 

[Petek]

You need to assume that a and m are relatively prime, right? If not, then a = 2 and m = 6 is a counterexample.

Hint: Do you know any formulas involving congruences and the phi function?

 

[disregardthat]

By modulo arithmetic this is equivalent to a^{phi(m)}=1 (mod m) where I have assumed that a and m are relatively prime. This result is well-known, but if you want to prove it (and I suggest you to do this) I would suggest that you

1) prove it for primes (fermats little)
2) prove it for powers of primes (use 1) + binomial formula)
3) prove it by induction on m (split up m in relatively prime factors, if its not possible use 2) )

You should be familiar with the multiplicative properties of phi. It is also essential that you know the fact that if x = 1 mod a, x = 1 mod b, then x = 1 mod ab whenever a and b are relatively prime. This is easily verified.

alternatively you could follow the same lines as in the proof of fermats little.

 

[oszust001]

Ok but what can I say for nonprincipal numers? how can I show that the equation has sens for every numbers not only for principal