How to prove $a^{k\times \phi(n)+1} \equiv a\ (mod\ n$)?

48 Views Asked by At

Sorry for my poor question, but I cannot prove this even if it looks so easy..
I know $a^{\phi(n)} \equiv 1\ (mod\ n)$, but how can I compute $a^{k\times \phi(n)}\ (mod\ n)$?

1

There are 1 best solutions below

3
On BEST ANSWER

Hint:

$$a^{k\phi(n)} = \left(a^{\phi(n)}\right)^k\equiv ...$$