I don't know how it works, although I learn it by myself. I need to find the last three digit number 3^3^3^3.... power of 3 is reapeted 2016 times. First of all, I calculated the Totient function for 1000. φ(1000)=400 after many calculations I've get this
3^187≡? (mod 1000)
Admittedly, I read a few books and article, but I still don't know how to overcome this obstecles.
$\endgroup$ 31 Answer
$\begingroup$If understand your question, you want to compute the last three digits in base $10$ of $3^{2016}$. To do this, you compute the residue of $3^{2016}$ modulo $1000$, which is fine. By Euler's Theorem, we know that $3^{400} \equiv 1 \;(1000)$, because $\varphi(1000) = 400$, as you pointed out. This gives $$3^{2016} \equiv 3^{5\cdot400 + 16}\equiv 3^{16}\; (1000)$$ Now you only need to compute $3^{16}$ modulo $1000$. You can compute this by hand, after observing that $3^{16} = 9^8 = (1 - 10)^8$ and then using the binomial theorem to expand the last term (you only need to do it up to degree 2): $$3^{16} \equiv (1 - 10)^8 \equiv 1 - 8\cdot 10 + 28 \cdot 10^2 \equiv 721 \; (1000)$$ Hence the answer is $721$.
$\endgroup$
