Determination of the last three digits of $2014^{2014}$

May I know if my proof is correct?

Consider $x$ such that $2014^{2014} \equiv x \pmod{1000}.$

By Euler's theorem, $2014^{\ \psi(1000)} =2014^{\ \psi(2^3)\psi(5^3)}=2014^{400}\equiv 1 \pmod{1000}$.

It follows that $2014^{2000} \equiv 1 \pmod{1000},$ hence $2014^{\ 14} \equiv x \pmod{1000}.$

By Binomial expansion, $2014^{\ 14} = 14^{\ 14}+2000m$, for some positive integer $m$.

Finally$, 14^{14} \equiv x \pmod{1000} \Longleftrightarrow \ x= 16$ and the last three digits are $016.$

In general, could we use the above method to determine the exact value of $n^n, \forall n \in \mathbb{N} ?$

Thank you and wish you a successful 2014!

Solution 1:

Carmichael function, Euler's totient theorem and Fermat's little theorem need $(a,m)=1$ for $a^n\equiv1\pmod m$ where $n$ may have different values in each case.

But $(2014,1000)=2>1$

As $\displaystyle1000=8\cdot125$

Clearly, $\displaystyle2014^{2014}\equiv0\pmod{2^3}\ \ \ \ (1)$

As $2014\equiv14\pmod{125},\displaystyle 2014^{2014}\equiv14^{2014}\pmod{125}$

As $\phi(125)=100, 2014\equiv14\pmod{100};\displaystyle 14^{2014}\equiv14^{14}\pmod{125}$

Now, $14^{14}=2^{14}\cdot7^{14}$

and $\displaystyle2^7=128\equiv3\pmod{125}\implies 2^{14}\equiv3^2\equiv9$

$\displaystyle7^{14}=(7^2)^7=(50-1)^7\equiv-1+\binom7150\pmod{125}\equiv99$

$\displaystyle\implies 14^{14}\equiv99\cdot9\pmod{125}\equiv16\ \ \ \ (2)$

Now apply the famous CRT on $(1),(2)$

Solution 2:

Your proof is not correct because you have to treat the moduli $8$ and $125$ separately (because $8$ and $2014$ are not relatively prime), and use (a very simple case of) the Chinese remainder theorem to deduce the answer. If you do so, you will see that it does not change your result ($16$). Also, you should write $\varphi$ instead of $\psi$.

Solution 3:

You cannot directly apply Euler's theorem because $\,2104\,$ is not coprime to your modulus $\,1000.\,$ But your argument is quickly patched. It shows that $\, n := 2014^{2014}\!\equiv 16\pmod {125}$ and, since $\,8\mid n,\,$ also $\,n\equiv 16\pmod 8\,$ thus $\,n \equiv 16\,$ mod lcm $\!(8,25) = 8\cdot 125 = 1000.$