How would we go about finding the last digit of very large numbers, such as ?
There are a variety of different tools that we can use, including modular arithmetic and the Chinese remainder theorem, which I am going to talk about in today’s post.
A problem like this can be tackled by listing out the initial expansions of a power in order to determine a pattern. Then, by proving that this pattern holds (often by induction), the last decimal digit of a power can be solved completely. For example, the last digit of various powers of 1 to 9 are:
From this we can determine that:
- the last digit of powers of 1 is always 1;
- the last digits of powers of 2 repeat in a cycle of 4, 8, 6, 2;
- the last digits of powers of 3 repeat in a cycle of 9, 7, 1, 3;
- the last digits of powers of 4 alternate between 6 and 4;
- the last digit of powers of 5 is always 5;
- the last digit of powers of 6 is always 6;
- the last digits of powers of 7 repeat in a cycle of 9, 3, 1, 7;
- the last digits of powers of 8 repeat in a cycle of 4, 2, 6, 8;
- the last digits of powers of 9 alternate between 1 and 9.
Find the last digit of 2^2016.
The last digits of the powers of two repeat in a cycle of 4, 8, 6, 2. Dividing 2016 by 4 we get 504 (with no remainder). Hence the sequence of digits repeats 504 times with no extra entries, so the last digit should be 6.
The above idea can be expressed more elegantly with modular arithmetic. Finding the last digit of a number is the same as finding the remainder when this number is divided by 10. In general, the last digit of a power in base n is its remainder upon division by n. So, for decimal numbers, we compute mod 10 to find the last digit, mod 100 to find the last two digits, etc.
Chinese Remainder Theorem
The Chinese Remainder Theorem states that
“if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime“
Applying this theorem, we can find a number mod 2^n and mod 5^n and then combine those results to find that number mod 10^n.
Find the last two digits of 74^540.
Observe that 100 = 4 x 25 and gcd(4,25) = 1. So we can compute 74^540 mod 4 and mod 25, then combine these to find it mod 100.
74^540 ≡ 2^540 x 37^540 ≡ 0 (mod 4)
7^540 ≡ (-1)^540 ≡ 1 (mod 25)
The unique solution mod 100 to x ≡ 0 (mod 4), x ≡ 1 (mod 25) is 76, so this is the answer.
Euler’s Theorem states that
“if n and a are coprime positive integers, then
where is Euler’s totient function.”
So an exponent b can be reduced modulo φ(n) to a smaller exponent without changing the value of a^b (mod n).
Find the last two digits of 33^42.
φ(100) = 40, so 33^40≡ 1 (mod 100). So, 33^42 ≡ 33^2 (mod 100). This is easier to compute: 33^2 = 1089, so answer is 89.
Another method is to expand the power using the Binomial theorem in such a way that many of the terms vanish mod 10. This is generally only useful when the base of the exponent is of the form 10k +/- 1.
Find the last two digits of 31^25.
After the second term, every term contains at least 2 zeros, and so they vanish mod 100. The first two terms = 751 ≡ 51 (mod 100) and so the last two digits of 31^25 are 51.
Hope you enjoyed this slightly longer post! M x