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 or 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:
From the table,we can see the following:
The set of last digits of powers forms a periodic sequence with periods given by the table below:
Find the last digit of .
Notice the pattern of the last digits. They are . The last digit repeats in a pattern that is 4 digits long: .
Note that divided by is with a remainder of so the pattern will repeat times, with two extra entries at the end. These last two entries are and so the last digit of is .
Find the last digit of .
The last digit of the powers of repeat in a cycle of . Dividing by we get as the quotient with as the remainder. Therefore, the sequence of digits repeats times with no extra entries, so the last digit should be .
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 . In general, the last digit of a power in base is its remainder upon division by . For decimal numbers, we compute . Finding the last 2 digits of an integer amounts to computing it mod and finding the last digits amounts to computation .
Find the last digit of
Compute some powers of mod :
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 and mod and then combine those results, using the Chinese remainder theorem, to find that number mod .
Find the last two digits of .
Observe that and . So we can compute (mod 4) and (mod 25), and then combine those results to find mod 100. Now
The unique solution mod to and is so this is the answer.
So an exponent can be reduced modulo to a smaller exponent without changing the value of
Find the last two digits of
Since and it follows that which is easier to compute: so the answer is
Find the last three digits of
This number is and mod it depends on the exponent mod Now by Euler's theorem again, so we get
Using the Chinese remainder theorem, there is a unique number mod that is congruent to and namely
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 This can occasionally be useful for simplification, but it generally only helps dramatically when the base of the exponent is of the form
Find the last 2 digits of by using binomial expansion.
Notice that after the second term every term contains at least 2 zeroes. Hence, every term after the second term is divisible by .
For the first two terms,
So the last digits of are .
Consider the following problem: what is Euler's theorem allows us to reduce the exponent somewhat: since is prime, so 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 . Clearly has a unique base-2 expansion where . We can use this fact to decompose the congruence into easier ones:
Now make a table of where . This will only take computations, making this strategy far more efficient once you plug in these values into the product.
In the example, Some quick squaring gives
So the answer is which works out to