Prove that if $~(n)|m~$ then $~a^m ≡ 1(\mod n)~$

Question

Prove that if $~(n)|m~$ then $~a^m ≡ 1(\mod n)~$

I'm finding this hard for me to prove, I would more than appreciate help with this.

$~\gcd(a,n)=1~$; $~a,n,m∈\mathbb N~$ this is all I'm given, how do I do this?

Thank you very much for all the help

Answer 1

It folows from the following applied modularly:

• any power of 1 is 1

• $(a^b)^c=a^{bc}$

  Reversing the second, we have that, if have an exponent a multiple of $\varphi(n)$ then it can be written with the parenthesized exponent as $\varphi(n)$

Evaluation of the parentheses gives 1 anytime $a$ is coprime to $n$

It then follows from our first rule (exchanging equals sign for congruence) that the new expression is congruent to 1.