Large exponential modular

Question

Proof $2011^{2011^{2011}}-2011 \equiv 0 \mod 30030$

By Chinese Remainder Theorem this is equivalent to proving:

$2011^{2011^{2011}}-2011 \equiv 0 \mod 2$

$2011^{2011^{2011}}-2011 \equiv 0 \mod 3$

$2011^{2011^{2011}}-2011 \equiv 0 \mod 5$

$2011^{2011^{2011}}-2011 \equiv 0 \mod 7$

$2011^{2011^{2011}}-2011 \equiv 0 \mod 11$

$2011^{2011^{2011}}-2011 \equiv 0$ mod $13$

$2011 \equiv 1 \mod (2,3,5)$ so $2011^{2011^{2011}}-2011 \equiv 1^{2011^{2011}}- 1 \equiv 0 \mod (2, 3,5)$

But I do not know how to continue.

Answer 1

The first three cases are quite simple, since $2011\equiv 1 \mod 2,3,5$, so $$2011^{2011^{2011}}-2011\equiv 1^{2011^{2011}}-1=1-1=0 \mod 2,3,5$$ The other cases can be treated like that (I'll only do $7$, the others are similar):

As $(7,2011)=1$, Euler's theorem applies, which tells $$2011^{\varphi(7)}=2011^6\equiv 1 \mod 7$$ So if we write $2011^{2011}=6q+r$, then $$2011^{2011^{2011}}=2011^{6q+r}=(2011^{6})^q\cdot 2011^r\equiv 1^q\cdot 2011^r\equiv 2011^r \mod 7$$ Again, as $(6,2011)=1$, apply Euler's theorem: $$2011^{\varphi(6)}=2011^2\equiv 1 \mod 6$$ So, as before: $$2011^{2011}=2011^{2*1005+1}\equiv 2011\equiv 1 \mod 6$$ Now $2011^{2011}=6q+1$ for some $q$, so $$2011^{2011^{2011}}\equiv 2011^1\equiv 2011$$

Answer 2

If $(n,2011)=1$ for any integer $n,$

$2011^{2011^{2011}}-2011\equiv0\pmod n\iff 2011^{(2011^{2011}-1)}-1\equiv0\pmod n$

Now $2011^{(2011^{2011}-1)}-1$ is divisible by $2011-1=2010=2010\cdot10=67\cdot5\cdot3\cdot2$ i.e., is divisible by $67,5,3,2$

$1:$ Using Fermat's Little Theorem, the sufficient condition for $2011^{(2011^{2011}-1)}\equiv1\pmod p$ for any prime $p\ne2011$ is $p-1$ divides $(2011^{2011}-1)$

Observe that $(2011^{2011}-1)$ is divisible by $2011-1=2010=2010\cdot10=67\cdot5\cdot3\cdot2$ i.e., is divisible by $6=7,10$ leading to $p=6+1=7,10+1=11$

Now as $2011\equiv9\equiv3^2\pmod{13},$

$2011^{(2011^{2011}-1)}\equiv (3^2)^{(2011^{2011}-1)}\pmod{13}$

$2011^{(2011^{2011}-1)}\equiv3^{2(2011^{2011}-1)}\equiv 1\pmod{13}$ if $12$ divides $2(2011^{2011}-1)\iff 6|(2011^{2011}-1)$ which we have proved already.

---

$2:$ Alternatively, $7\cdot11\cdot13=1001,2011\equiv9\equiv3^2\pmod {1001}$

$\implies 2011^{(2011^{2011}-1)}\equiv 3^{2(2011^{2011}-1)}\pmod {1001}$

Using Carmichael's Theorem, the sufficient condition for $3^{2(2011^{2011}-1)}\equiv1\pmod {1001}$ is $\lambda(1001)$ divides $2(2011^{2011}-1)$

Now, $\lambda(1001)=$lcm$(\lambda(7), \lambda(11), \lambda(13))=$lcm$(6,10,12)=60$

Now, $2(2011^{2011}-1)$ is divisible by $2(2011-1)=2(67\cdot5\cdot3\cdot2)$ which is divisible by $60$