What is $25^4 mod 39$ congruent to?

Question

My result is $25^4 \equiv 25 (\textrm{mod}\ 39)$, but Wolfram Alpha simplifies $25^4 \ \textrm{mod}\ 39$ as 1. How should I interpret this?

I have the following idea:

$25^4 \equiv 1 (\textrm{mod}\ 39)$

But I don't have an explanation for it.

Answer 1

Since $25^2 = 625 = 16\cdot 39 + 1$, we have that $25^2 \equiv 1 \pmod{39}$. Hence $25^4 = (25^2)^2 \equiv (1)^2 \equiv 1 \pmod{39}$

Answer 2

${\rm mod}\ 3,13\!:\ 25^4\equiv (\color{#c00}{\pm1})^4\equiv 1,\,$ so $\ 3,13\mid 25^4-1\,\Rightarrow\,{\rm lcm}(3,13)=39\mid25^4-1\ \ $ QED

Remark $\ $ Answering a question posed in a comment: I decomposed $\,39 = 3\cdot13\,$ because it was clear that this would simplify the computation of $\,25^n \pmod{39}\,$ given that the base $25$ satisifies $\,25\equiv\color{#c00} 1\pmod{3}\,$ and $\,25\equiv \color{#c00}{-1}\pmod{13}.\,$ Both $\,\color{#c00}1\,$ and $\,\color{#c00}{-1}\,$ are numbers whose powers are trivial to compute, so this greatly simplifies the computation.

Essentially the above employs a special case of the Chinese Remainder Theorem (CRT). This theorem gives an algebraic method to "divide and conquer", i.e. to decompose modular arithmetic to arithmetic in simpler modular rings, then combine the simpler solutions into a solution to the original problem. When you learn ring theory the innate structure behind CRT will become much clearer, being revealed as an explicit ring isomorphism with a product ring.