Compute $5^{15}$ mod $7$ using the fact that if gcd$(a,n) = 1$, then $a^{\phi(n)}$ mod $n$ = $1$ (Euler-phi function).

Question

Compute $5^{15}$ mod $7$ using the fact that if gcd$(a,n) = 1$, then $a^{\phi(n)}$ mod $n$ = $1$ (Euler-phi function).

I see that $5^{15} = 5^{6}5^{6}5^{3} = 5^{\phi(n)}5^{\phi(n)}5^{3}$, but I'm not sure if this would help.

Answer 1

You've already shown $5^{15}=5^{6}\cdot5^{6}\cdot5^{3}=5^{\phi(7)}\cdot5^{\phi(7)}\cdot5^{3}$.

By Euler's theorem, $\gcd(5,7)=1\implies5^{\phi(7)}\equiv1\pmod7$.

Therefore, $5^{\phi(7)}\cdot5^{\phi(7)}\cdot5^{3}\equiv1\cdot1\cdot5^3\equiv125\equiv6\pmod7$.

Answer 2

Hint:

Since $5^6\equiv 1\mod 7$, we have $\;5^{15}\equiv5^{15\bmod 6}=5^3$.