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.

### Pattern Finding

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.

ExampleFind the last digit of 2^2016.

The last digits of the powers of two repeat in a cycle of 2, 4, 8, 6. 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.

### Modular Arithmetic

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.

For example,

### 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 arepairwise coprime“– Wikipedia

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*.

ExampleFind 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)

and

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

Euler’s Theorem states that

“if n and a are coprime positive integers, then

where is Euler’s totient function.”-Wikipedia

So an exponent *b* can be reduced modulo φ(n) to a smaller exponent without changing the value of *a^b (mod n).*

ExampleFind 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.

### Binomial Expansion

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**.

ExampleFind 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