Exponentiation Modulo N

Modulo Arithmetic : Last digit analysis (Part $1$)

Previous part

Ok, so how did we figure it out? Let's review the basic properties of modulo arithmetic.

Indeed, the last digit of $2014^{2014}$ is the same as the last digit of $4^{2014}$, since $2014 \equiv 4 \pmod{10}$. In general, if we want to find the last digit of something like $10129131^{1021313}$, we just need to find the last digit of $1^{1021313}$, which is evidently $1$. So, we just need the last digit for the powers of the single-digit numbers.

Note that the last digit of powers of $1, 5, 6$ are always $1, 5, 6$ respectively. Why? Because $1 \times 1 = 1$, $5 \times 5 \equiv 5 \pmod{10}$, and $6 \times 6 \equiv 6 \pmod{10}$! So, we always get the same last digit by exponentation.

Things are a bit messier for the remaining powers, but we can still work things out!

For powers of $2$ :

$2^1 = 2$, $2^2 = 4$, $2^3 = 8$, $2^4 \equiv 6 \pmod{10}$, $2^5 \equiv 2 \pmod{10}$, $2^6 \equiv 4 \pmod{10}$.

That's right. In fact, these also happens for other powers. For instance, the cycle is $3, 9, 7, 1, 3, 9, ...$ for powers of $3$. See if you can work out the cycles for the remaining powers :

and finally,

Great, seems like you know what's going on here. In the next part we'll look at the applications of last digit analysis.

Next part

Of course not! That would require too much work. We would use repeated squaring, which is much more efficient than the standard multiplication. First, we figure out what the exponent's binary representation is. $39_{10}=100111_2=32+4+2+1$.

Now we just repeatedly square the base modulo $11$. $2^1\equiv 2\pmod{11}$ $2^2= 2^1\cdot2^1\equiv 4\pmod{11}$ $2^4= 2^2\cdot2^2\equiv 5\pmod{11}$ $2^8= 2^4\cdot2^4\equiv 3\pmod{11}$ $2^{16}= 2^8\cdot2^8\equiv 9\pmod{11}$ $2^{32}= 2^{16}\cdot2^{16}\equiv 4\pmod{11}$

Now, we know that $2^{39}\equiv2^{32}\cdot2^4\cdot2^2\cdot2^1\equiv4\cdot5\cdot4\cdot2\equiv6\pmod{11}.$This only requires about 7 multiplications compared to the 38 if we were to multiply it out.