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

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.

I'm assuming there's an interstitial step I'm missing. All I know is that $5^{15}$ mod $7$ = $5^{\phi(7)}5^{\phi(7)}5^{3}$ mod $7$. — Oliver G, Jul 28 '16 at 13:47
You didn't completely use the "fact", i.e. you didn't use that $\,5^{\varphi}\equiv 1\,$ to simplify further. Doing so you get $\, 5^{15}\equiv 1\cdot 1\cdot 5^3,\ $ by using standard congruence arithmetic, here the [congruence produce rule.](http://math.stackexchange.com/a/879262/242) — Bill Dubuque, Jul 28 '16 at 13:52

Bernard · Answer 1 · 2016-07-28T16:26:01.817

1

Hint:

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

edited Jul 28 '16 at 16:26

answered Jul 28 '16 at 13:42

Bernard

Hope you don’t mind, but I stuck in the value of $5^6$ for you. I would also recommend using the TeX for congruence (\equiv) rather than the equality sign. But it would’ve been over-editing to do that for you. – Lubin Jul 28 '16 at 16:17
I'd rather thank you – I'm familiar with typos… The equality signs problems come from usually thinking in the quotient ring. – Bernard Jul 28 '16 at 16:24

score 1 · Accepted Answer · answered Jul 28 '16 at 16:25

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$.

2 Answers2