Finding the Last Digit of a Power

Many mathematical contests ask students to find the last digit (or digits) of a power. In most cases, the powers are quite large numbers such as $6032^{31}$ or $89^{47},$ so that computing the power itself is out of the question.

However, there are a number of tools, such as modular arithmetic, the Chinese remainder theorem, and Euler's theorem that serve as shortcuts to finding the last digits of an expanded power. Solving these types of problems gives a down-to-earth introduction to these techniques of elementary number theory.

A common way to attack these type of questions is to list out the initial expansions of a power to determine a pattern. Questions which ask about the last decimal digit of a power can be solved completely after proving that the pattern in question holds (often by induction). The last digits of various powers of an integer are given in the table below:

$$\begin{array} { c | c c c c } \text{digit } d & d^2 & d^3 & d ^ 4 & d^ 5\\ \hline 1 & 1 & 1 & 1 & 1 \\ 2 & 4 & 8 & 6 & 2 \\ 3 & 9 & 7 & 1 & 3 \\ 4 & 6 & 4 & 6 & 4 \\ 5 & 5 & 5 & 5 & 5 \\ 6 & 6 & 6 & 6 & 6 \\ 7 & 9 & 3 & 1 & 7 \\ 8 & 4 & 2 & 6 & 8 \\ 9 & 1 & 9 & 1 & 9 \\ \end{array}$$ From the table,we can see the following:

$$\begin{array} {|c|c|} \hline \text{The last digit of powers of 1 is always} & 1\\ \hline \text{The last digits of powers of 2 repeat in a cycle of} & 4,8,6,2\\ \hline \text{The last digits of powers of 3 repeat in a cycle of} & 9,7,1,3\\ \hline \text{The last digits of powers of 4 repeat in a cycle of} & 6,4\\ \hline \text{The last digit of powers of 5 is always} & 5\\ \hline \text{The last digit of powers of 6 is always} & 6\\ \hline \text{The last digits of powers of 7 repeat in a cycle of} & 9,3,1,7\\ \hline \text{The last digits of powers of 8 repeat in a cycle of} & 4,2,6,8\\ \hline \text{The last digits of powers of 9 repeat in a cycle of} &1,9\\ \hline \end{array}$$

The set of last digits of powers forms a periodic sequence with periods given by the table below:

$$\begin{array} { c | c } \text{Digit } & \text{Period}\\ \hline 0,1,5,6 & 1 \\ 2,3,7,8 & 4 \\ 4,9 & 2 \\ \end{array}$$

Find the last digit of $7^{358}$.

---

Notice the pattern of the last digits. They are $7,9,3,1,7,9,3,1,7,9,\ldots$. The last digit repeats in a pattern that is 4 digits long: $7,9,3,1$.

Note that $358$ divided by $4$ is $89$ with a remainder of $2,$ so the pattern will repeat $89$ times, with two extra entries at the end. These last two entries are $7$ and $9,$ so the last digit of $7^{358}$ is $9$. $_\square$

Find the last digit of $2^{2016}$.

---

The last digit of the powers of $2$ repeat in a cycle of $2,4,8,6,2,4,8,6,\ldots$. Dividing $2016$ by $4,$ we get $504$ as the quotient with $0$ as the remainder. Therefore, the sequence of digits repeats $504$ times with no extra entries, so the last digit should be $6$. $_\square$

Main article: Modular Arithmetic

The patterns of the previous section can be expressed elegantly in the language of modular arithmetic. Finding the last digit of a positive integer is the same as finding the remainder of that number when divided by $10$. In general, the last digit of a power in base $n$ is its remainder upon division by $n$. For decimal numbers, we compute $\bmod~{10}$. Finding the last 2 digits of an integer amounts to computing it mod $100,$ and finding the last ${n}$ digits amounts to computation $\bmod~10^{n}$.

Find the last digit of $17^{17}.$

---

Compute some powers of $17$ mod $10$:

$$17^2\equiv 7^2 \equiv 9 \pmod{10},$$

so

$$17^4 \equiv 9^2 \equiv 1 \pmod{10}.$$

Therefore, $17^{17} = \big(17^4\big)^{4}\times 17$ and

$$\begin{aligned} 17^{17}&\equiv \big(17^4\big)^{4}\times 17\pmod{10}\\ &\equiv 1^4\times 17\pmod{10}\\ &\equiv 7 \pmod{10}.\ _\square \end{aligned}$$

The Chinese remainder theorem is a powerful tool to find the last few digits of a power. The idea is to find a number mod $5^n$ and mod $2^n,$ and then combine those results, using the Chinese remainder theorem, to find that number mod $10^n$.

Find the last two digits of $74^{540}$.

---

Observe that $100=4\times 25$ and $\text{gcd}(4,25)=1$. So we can compute $74^{540}$ (mod 4) and $74^{540}$ (mod 25), and then combine those results to find $74^{540}$ mod 100. Now

$$\begin{aligned} 74^{540}\equiv 2^{540}\times 37^{540}& \equiv 0 \pmod{4}\\ 74^{540}\equiv (-1)^{540}&\equiv 1\pmod{25}. \end{aligned}$$

The unique solution mod $100$ to $x\equiv 0 \pmod 4$ and $x\equiv 1 \pmod{25}$ is $76,$ so this is the answer. $_\square$

Large exponents can be reduced by using Euler's theorem: if $\gcd(a,n) = 1$ and $\phi(n)$ denotes Euler's totient function, then

$$a^{\phi (n)}\equiv 1 \pmod{n}.$$

So an exponent $b$ can be reduced modulo $\phi(n)$ to a smaller exponent without changing the value of $a^b\pmod n.$

Find the last two digits of $33^{42}.$

---

Since $\phi(100)=40$ and $33^{40} \equiv 1\pmod{100},$ it follows that $33^{42}\equiv 33^2 \pmod{100},$ which is easier to compute: $33^2 = 1089,$ so the answer is $89.$ $_\square$

Find the last three digits of $4^{2^{42}}.$

---

This number is $0\pmod{2^3},$ and mod $5^3$ it depends on the exponent mod $\phi(5^3) = 100.$ Now $2^{42} \equiv 2^2 \equiv 4 \pmod{100}$ by Euler's theorem again, so we get $4^4 =256 \equiv 6\pmod{125}.$

Using the Chinese remainder theorem, there is a unique number mod $1000$ that is congruent to $0\pmod{8}$ and $6\pmod{125},$ namely $256.$ $_\square$

Another approach (similar to computations involving Hensel's lemma) is to expand the power using the binomial theorem, in such a way that many of the terms vanish modulo powers of $10.$ This can occasionally be useful for simplification, but it generally only helps dramatically when the base of the exponent is of the form $10k\pm 1.$

Find the last 2 digits of $31^{25}$ by using binomial expansion.

---

We have

$$31^{25} = (1+30)^{25}= 1^{25} + \dbinom{25}{1}\times 1^{24} \times 30 +\dbinom{25}{2}\times 1^{23} \times 30^2+ \cdots + \dbinom{25}{25} \times 30^{25}.$$

Notice that after the second term every term contains at least 2 zeroes. Hence, every term after the second term is divisible by $100$.

For the first two terms,

$$1+25\times 30=751 \equiv 51 \pmod{100}.$$

So the last $2$ digits of $31^{25}$ are $51$. $_\square$

Consider the following problem: what is $117^{1023} \pmod{229}?$ Euler's theorem allows us to reduce the exponent somewhat: since $229$ is prime, $\phi(229)=228,$ so $117^{1023} \equiv 117^{111} \pmod{229}.$ This still seems to be a difficult computation.

In cases like these, repeated squaring is often the easiest way to do the required computation. Suppose we want to evaluate $x^a \pmod{n}$. Clearly $a$ has a unique base-2 expansion $(a_1 a_2 \cdots a_k)_2,$ where $a_i =0,1$. We can use this fact to decompose the congruence into easier ones:

$$x^a \equiv x^{(a_1 a_2 \cdots a_k)_2} \equiv \prod_{a_i \neq 0}^{}{x^{2^{k-i}}} \pmod{n}.$$

Now make a table of $x^{2^i},$ where $i\le k$. This will only take $\big\lfloor\log_2(a)\big\rfloor$ computations, making this strategy far more efficient once you plug in these values into the product.

In the example, $111 = 2^6+2^5+2^3+2^2+2^1+2^0.$ Some quick squaring gives

$$\begin{aligned} 117^1 &\equiv 117 \\ 117^2 &\equiv 178 \\ 117^4 &\equiv 82 \\ 117^8 &\equiv 83 \\ 117^{16} &\equiv 19 \\ 117^{32} &\equiv 132 \\ 117^{64} &\equiv 20. \end{aligned}$$

So the answer is $117 \cdot 178 \cdot 82 \cdot 83 \cdot 132 \cdot 20 \pmod{229},$ which works out to $141.$

• Primitive Roots

• RSA Encryption

• Euler's Totient Function