Large powers

Number Theory Level 4

$\LARGE { 2015 }^{ { 2016 }^{ 2017 } }$

What is the remainder when the number above is divided by 11?

The answer is 9.

1 solution

Dylan Pentland
Jun 8, 2015

First, we simplify a little bit to get rid of $2015$ : $\displaystyle { 2015 }^{ { 2016 }^{ 2017 } }\equiv { 2 }^{ { 2016 }^{ 2017 } } \pmod {11}$ Now, we need to find the period of ${2}^{n} \pmod{11}$ . Since $\gcd(2,11)=1$ , we know that ${2}^{\phi(11)} \equiv 1 \pmod{11}$ . $11$ is prime so $\phi(11)=10$ . We now need to find ${2016}^{2017}\pmod{10}$ : ${2016}^{2017} \equiv {6}^{2017} \pmod{10} \equiv 6 \pmod{10}$ Hence, ${ 2015 }^{ { 2016 }^{ 2017 } }\equiv { 2 }^{ 6 } \pmod {11}$ which is just $\boxed{9}$ .

Moderator note:

For clarity, can you elaborate on this line?

$\ldots \equiv {6}^{2017} \pmod{10} \equiv 6 \pmod{10}$

Challenge master note:

As ${6}^{2}\equiv6\pmod{10}$ we know that ${6}^{k}\equiv6\pmod{10}$ .

Dylan Pentland - 6 years ago

If I understand your comment correctly, what you're trying to imply is to prove it by induction. In that case, you should also show the inductive step to make the solution clearer:

$6^{k+1}=6\times 6^k\equiv 6\times 6\equiv 36\equiv 6\pmod{10}$

There's also a more direct approach to prove that claim using Fermat's Little Theorem as follows:

$\forall~k\in\Bbb{Z^+}~,~6^k\equiv\begin{cases}(2\times 3)^k\equiv 0\pmod2\\ (5+1)^k\equiv 1^k\equiv 1\pmod5\end{cases}$

$1\bmod 5$ implies that the remainder modulo $10$ is either $1$ or $6$ . Since we also have $0\bmod 2$ and $1$ is odd, the remainder modulo $10$ is obviously $6$ .

$\therefore\quad 6^k\equiv 6\pmod{10}~\forall~k\in\Bbb{Z^+}$

Prasun Biswas - 6 years ago

I wasn't actually thinking inductively, but that approach is pretty much equivalent. I was thinking more along the lines of the period of ${6}^{k}$ in modulo 10 is 1, and therefore ${6}^{1}\equiv{6}^{2}\equiv{6}^{3}...\equiv{6}^{k}\pmod{10}$ .

Dylan Pentland - 6 years ago

By the way, there's really no need to invoke totient function.

Fermat's Little Theorem works just fine. We have $a^{10}\equiv 1\pmod{11}$ for any integer $a$ coprime to $11$ since $11$ is a prime.

Although, frankly speaking, there's not much difference between the two since Euler's Theorem is simply the generalization of Fermat's Little Theorem.

Prasun Biswas - 6 years ago

Large powers

The answer is 9.

1 solution

Moderator note:

0 pending reports