# $\left (14^{2014} \right )^{2014} \mod 60$ without a calculator

Calculate without a calculator:

$\left (14^{2014} \right )^{2014} \mod 60$

I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1.

This was my solution so far (also doesn't really work without a calculator):

Prime factorization of 60:
$60 = 2^{2}\cdot 3\cdot 5$

Chinese Remainder Theorem setup:
$\left (14^{2014} \right )^{2014} \mod 4\\$
$\left (14^{2014} \right )^{2014} \mod 3\\$
$\left (14^{2014} \right )^{2014} \mod 5\\$

Euler's Theorem:
$\phi \left ( 4 \right ) = 2$
$\Rightarrow 14^{2}\equiv 1 \mod 4$

Whoops, that's not right because gcd(14,4) is not 1, but 2. Euler's Theorem only works when gcd(a,m) = 1.

I don't know how else to solve this, does anyone have an idea?

$$X=\large (14^{2014})^{2014}=14^{2014^2}$$

Now, $60=3\times 4\times 5$. Now,

$$X\equiv\begin{cases}(-1)^{2014^2}\equiv 1\pmod3\\ (-1)^{2014^2}\equiv 1\pmod5\\ 7^{2014^2}\cdot 4^{(2014^2)/2}\equiv 0\pmod4\end{cases}$$

Now, use Chinese Remainder Theorem.

• You don't need to use CRT, with $X \equiv1 \pmod 3, X \equiv1 \pmod 5$, i'ts obvious that $X \equiv 1 \pmod{15}$, find the next number that is a multiple of 4 yields $\boxed{16}$. – GohP.iHan May 3 '15 at 8:57
• Thank you, this helped the best! – Thursday Next May 3 '15 at 9:00
• @GohP.iHan, you're absolutely right but I just find using CRT a bit more natural. I'm not that much used to exhaust my brain like you do. :3 There's a reason you're the genius, not me. – Prasun Biswas May 3 '15 at 9:00
• @CGuy, happy to help. :) – Prasun Biswas May 3 '15 at 9:01
• Haha, stop complimenting me man. Somemore, you don't need to split 60 into all prime factors, as long as they are coprime to each other: $60 = 15 \times 4$. We immediately get $X \equiv (-1)^\text{even} \equiv 1 \pmod{15}$ – GohP.iHan May 3 '15 at 9:07

$$\left (14^{2014} \right )^{2014}=(14^2)^{1007\times2014}\equiv 16^{1007\times2014} \mod 60$$

Next, notice that $16\times 16\equiv 16\pmod{60}$ to conclude $16^n\equiv 16\pmod{60}$ for all integers $n\ge 1$

With all the powers of $2$, $(14^{2014})^{2014}$ is clearly equivalent to $0\pmod4$. We also have $(14^{2014})^{2014}\equiv[(-1)^{2014}]^{2014}\equiv 1\pmod{15}$. These $2$ conditions combined yield a result equivalent to $16\pmod{60}$.

As $(a^m)^n=a^{mn},$

we need $14^{2014^2}\pmod{60}$

As $(14^n,60)=2^2$ for integer $n\ge2,$

let us compute $14^{2014^2-2}\pmod{15}$

Now $14\equiv-1\pmod{15}\implies14^{2014^2-2}\equiv(-1)^{2014^2-2}\pmod{15}\equiv1$ as $2014^2-2$ is even

$\implies14^2\cdot14^{2014^2-2}\equiv14^2\cdot1\pmod{14^2\cdot15}$

As $60|14^2\cdot15,$
$$14^2\cdot14^{2014^2-2}\equiv14^2\pmod{60}\equiv ?$$

• What does (14^n, 60) = 2^2 stand for? There is no operator or anything. Otherwise I think I get it. – Thursday Next May 3 '15 at 9:04
• @CGuy, $(a,b)=\gcd(a,b)$ is the greatest common divisor of $a$ and $b$. – Prasun Biswas May 3 '15 at 9:05
• Ah okay I didn't know you could write it like that, thanks. – Thursday Next May 3 '15 at 9:06
• @CGuy, I actually prefer the $\gcd$ notation since it's understandable to all. People have different preferences when it comes to notations. – Prasun Biswas May 3 '15 at 9:07

Carmichael's function for $60$ is lcm$(\phi(4),\phi(3),\phi(5))=$ lcm$(2,2,4)=4$, so $a^k \equiv a^{k+4}$ once all possible prime factors of $60$ have been accumulated. So we can quickly square $14$ twice and see where it's going: $$14^2 = 196 \equiv 16 \bmod 60 \\ 14^4 \equiv 16^2 = 256 \equiv 16 \bmod 60$$ So we are fortunate here, and $14^{2k} \equiv 16^k \equiv 16 \bmod 60$. No need to worry about the second exponentiation, except to observe that the resulting exponent is certainly even.

By below $\ 2\mid 15-1\,\ \Rightarrow\,\ 14^{2k}\,\equiv\, 4(4^{-1}\,{\rm mod}\ 15)\equiv 4^2\!\pmod{4^2\!\cdot 15},\,\ j = 2\le 2k$.

Lemma $\,\ a\mid n\!-\!1\,\Rightarrow\,(n\!-\!1)^{2k}\equiv a^j(a^{-j}\ {\rm mod}\ n)\ \pmod{a^jn}\,$ if $\ 0\le \color{#c00}{j\le 2k}$

Proof $\$ Note $\, {\rm mod}\ n\!:\ (n\!-\!1)^{2k}\equiv (-1)^{2k}\equiv 1\equiv a^j(a^{-j}\ {\rm mod}\ n)$

$a\mid n\!-\!1\!\!\underset{\color{#c00}{j\,\le\, 2k}}\Rightarrow\! {\rm mod}\ a^j\!:\ (n\!-\!1)^{2k}\color{#c00}{\equiv 0}\equiv a^j(a^{-j}\ {\rm mod}\ n).\,$ Being congruent both mod $\,a^j\,$ & $\,n,\,$ they are also congruent mod $\,{\rm lcm}(a^j,n) = a^jn,\,$ by $\,(a,n)=1,\,$ by $\,a\mid n\!-\!1.$

• Remark $\,\ a\mid n\!-\!1\,\Rightarrow\, ab = n\!-\!1\,\Rightarrow\, a^{-1}\equiv -b\pmod{n},\,$ so no modular inversion is needed. – Bill Dubuque May 3 '15 at 19:20