Prove a^m = a^{m-\phi(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

 

[blue_raver22]

To prove this equation, we can use the fundamental theorem of arithmetic which states that any integer can be expressed as a unique product of prime numbers. We can also use the Euler's totient function, denoted as φ(m), which gives the number of positive integers that are less than m and relatively prime to it.

First, we can write a^m as a product of its prime factors, where each factor is raised to the power of m. So, we have a^m = (p_1^{m_1})(p_2^{m_2})...(p_k^{m_k}), where p_i are prime numbers and m_i are their respective powers.

Next, we can use the property of Euler's totient function which states that if a and m are relatively prime, then a^φ(m) ≡ 1 (mod m). This means that if we raise a to the power of φ(m), the result will be congruent to 1 (mod m).

Now, we can rewrite the equation a^m ≡ a^{m-\phi(m)} (mod m) as a^m ≡ (a^{φ(m)})^{m/φ(m)} ≡ 1^{m/φ(m)} ≡ 1 (mod m), since a and m are relatively prime.

Therefore, we have proven that a^m ≡ a^{m-\phi(m)} (mod m) using the fundamental theorem of arithmetic and Euler's totient function. This result can also be extended to any integer power, not just m, as long as a and m are relatively prime.