Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

Question

The question: Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

I used a modulo calculator to get that the answer for $N$ mod $4$ is $3$, and for $11$ it's $10$.

I got the right answer for $4$ using the Euclidean algorithm:

$2015 = 503 \times 4 + 3 = 3$ mod $4$. Thus I got that $2015^{2015}=3^{3}$ mod $4 = 27 $ mod $4 = 3$, and that was the remainder.

I tried the same method for $11$, got that $2015=2$ mod $11$, and then said that $2015^{2015}=2^{2}$ mod $11$, but this was wrong.

Any help is appreciated!

Answer 1

If $a\equiv b\pmod m,a^x\equiv b^x\pmod m$ where $x$ is any integer

and if $x\equiv y\pmod{\phi(m)},b^x\equiv b^y\pmod m$ (using Euler's Totient Theorem)

So,

as $2015\equiv2\pmod{11},$

$$\implies2015^{2015}\equiv2^{2015}\pmod{11}$$

Again as $2015\equiv5\pmod{11-1},$

$$2^{2015}\equiv2^5\pmod{11}$$