I need to explain why $5^4=1 \mod 12$ without actually calculating $5^4 \mod 12$. Since $5^4=(5^2)^2$ and $5^2=1 \mod 12$, it seems obvious that $5^4=1^2=1 \mod 12$. I'm wondering if there is a better way to answer this question though. Is there some trick or fact I'm forgetting that would allow me to explain this without computing $5^2 \mod 12$?
$\endgroup$ 24 Answers
$\begingroup$There isn't really a great deal to say - some calculation is necessary. But if you note that $\varphi(12)=4$ ie the count of the numbers less than $12$ which have no common factor with $12$ is $4$ (being $1,5,7,11$) it is immediate that any of these numbers raised to the power $4$ is equivalent to $1$ modulo $12$ from basic group theory, or the Fermat-Euler theorem.
You have to do as much work to prove those as to get the result you want. And in fact all the squares are equivalent to $1$, which is stronger than Fermat-Euler.
But Fermat-Euler applies in generality and saves work cross a range of cases.
$\endgroup$ $\begingroup$This seems like a perfectly good proof to me. If you think that your factorization goes against the spirit of the question though, there is another approach. Consider the multiplicative group $(\mathbb Z/12\mathbb Z)^\times$. What’s the cardinality of this group? What does that tell you about all if it’s elements?
If you haven’t done any group theory yet, my hint is the same as the one that’s been commented: Use Euler’s Theorem.
$\endgroup$ 4 $\begingroup$It's a fine justification, but the true reason is that $5$ and $12$ are coprime, so by Euler's theorem, $5^{\varphi(12)}\equiv 1\mod 12$, and it happens that $$\varphi(12)=\varphi(3)\cdot\varphi(4)=2\cdot 2.$$
$\endgroup$ $\begingroup$What you have is correct.
$5^2 = 1 \pmod {12}\\ 1^2 = 1 \pmod {12}\\ 5^4 = 1^2 = 1 \pmod {12}$
But if you want to get fancy you can invoke the Fermat-Euler theorem.
The set of numbers less than $12$ that are co-prime to $12$ form a cyclic group under multiplication modulo $12$.
There are 4 elements to this group.
Any element element in this group raised to the $4^{th}$ power equals the identity element.
More generally:
If $n$ has prime factorization $p_1^ip_2^j\cdots p_k^t$
$\phi(n) = n \frac {p_1 - 1}{p_1}\frac {p_2 - 1}{p_2}\cdots \frac {p_k - 1}{p_k}$
$\phi(n)$ is the number of elements co-prime to $n$
and if $\gcd (a,n) = 1$
$a^{\phi(n)} = 1 \pmod n$
$\endgroup$
