How To Find The Last Digit Of A Power

How would we become nigh finding the last digit of very big numbers, such every bit Screen Shot 2017-08-24 at 4.27.22 PM.png ?

At that place are a variety of different tools that we tin apply, including modular arithmetic and the Chinese remainder theorem, which I am going to talk nigh in today's post.

Design Finding

A problem like this can be tackled by listing out the initial expansions of a ability in order to decide a pattern. Then, by proving that this pattern holds (often past induction), the last decimal digit of a power tin can be solved completely. For instance, the last digit of diverse powers of i to 9 are:

Screen Shot 2017-08-24 at 4.32.26 PM.png — Source: Bright

From this we can make up one's mind that:

the concluding digit of powers of 1 is always i;
the final digits of powers of 2 repeat in a cycle of 4, 8, 6, 2;
the last digits of powers of iii repeat in a bicycle of 9, 7, 1, 3;
the last digits of powers of 4 alternating between 6 and 4;
the last digit of powers of 5 is always 5;
the terminal digit of powers of 6 is ever half-dozen;
the final digits of powers of 7 echo in a cycle of 9, 3, ane, seven;
the concluding digits of powers of viii echo in a bicycle of 4, two, 6, 8;
the terminal digits of powers of 9 alternating between ane and 9.

Example

Find the last digit of ii^2016.

The last digits of the powers of 2 echo in a wheel of 2, 4, 8, vi. Dividing 2016 by four we get 504 (with no remainder). Hence the sequence of digits repeats 504 times with no actress entries, so the last digit should be 6.

Modular Arithmetic

The in a higher place thought can be expressed more elegantly with modular arithmetic. Finding the last digit of a number is the aforementioned as finding the remainder when this number is divided past ten. In general, the terminal digit of a power in base n is its remainder upon partition past n. So, for decimal numbers, we compute mod 10 to find the final digit, mod 100 to find the last two digits, etc.

For example,

Screen Shot 2017-08-24 at 5.22.44 PM.png

Chinese Remainder Theorem

The Chinese Residual Theorem states that

"if one knows the remainders of the partitioning of an integer $due north$ by several integers, and so one tin can determine uniquely the remainder of the sectionalisation of $n$ by the product of these integers, under the condition that the divisors are pairwise coprime"

– Wikipedia

Applying this theorem, we can find a number mod 2^due north andmod v^due north and then combine those results to find that numbermod 10^north.

Example

Find the last two digits of 74^540.

Notice that 100 = 4 x 25 and gcd(4,25) = 1. Then we can compute 74^540 modern 4 and mod 25, and so combine these to notice it modern 100.

74^540 ≡ two^540 x 37^540 ≡ 0 (mod 4)

and

7^540 ≡ (-1)^540 ≡ 1 (mod 25)

The unique solution modernistic 100 to ten ≡ 0 (modern 4), 10 ≡ 1 (modern 25) is 76, then this is the answer.

Euler's Theorem

Euler'southward Theorem states that

"if n and a are coprime positive integers, so

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

where $\varphi (n)$ is Euler's totient part."

-Wikipedia

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

Example

Discover the last ii digits of 33^42.

φ(100) = forty, so 33^forty≡ i (mod 100). Then, 33^42 ≡ 33^ii (mod 100). This is easier to compute: 33^2 = 1089, and then answer is 89.

Binomial Expansion

Another method is to expand the power using the Binomial theorem in such a manner that many of the terms vanishmod ten. This is mostly only useful when the base of operations of the exponent is of the form 10k +/- one.

Example

Observe the concluding 2 digits of 31^25.

Afterward the second term, every term contains at least 2 zeros, then they vanish modernistic 100. The commencement two terms = 751 ≡ 51 (mod 100) and so the last two digits of 31^25 are 51.