"

If you raise any integer to the fifth power, its last digit doesnt change. For example, 2 ^{ 5 } = 32.

Its easy to prove this assertion by brute force. Since the last digit of * b * ^{ n } only depends on the last digit of * b * , its enough to verify that the statement above holds for 0, 1, 2, , 9.

Although thats a valid proof, its not very satisfying. Why fifth powers? Were implicitly working in base 10, as humans usually do, so what is the relation between 5 and 10 in this context? How might we generalize it to other bases?

The key is that 5 = (10) + 1 where ( * n * ) is the number of positive integers less than * n * and relatively prime to * n * .

Euler discovered the function and proved that if * a * and * m * are relatively prime, then

* a * ^{ ( m ) } = 1 (mod * m * )

This means that * a * ^{ ( m ) } 1 is divisible by * m * . (Technically I should use the symbol (U+2261) rather than = above since the statement is a congruence, not an equation. But since Unicode font support on various devices is disappointing , not everyone could see the proper symbol.)

Eulers theorem tells usthatif * a * is relatively prime to 10 then * a * ^{ 4 } ends in 1, so * a * ^{ 5 } ends in the same digit as * a * . That proves our original statement for numbers ending in 1, 3, 7, and 9. But what about the rest, numbers that are divisible by 2 or 5? Well answer that question and a little more general one at the same time. Let * m * = where and are distinct primes. In particular, we could choose = 2 and = 5; We will show that

* a * ^{ ( m )+1 } = * a * (mod * m * )

for all * a * , whether relatively prime to * m * or not. This would show in addition, for example, that in base 15, every number keeps the same last digit when raised to the 9th power since (15) = 8.

We only need to be concerned with the case of * a * being a multiple of or since Eulers theorem proves our theorem for the rest of the cases. If * a * = our theorem obviously holds, so assume * a * is some multiple of , * a * = * k * with * k * less than (and hence relatively prime to ).

We need to show that divides ( * k * ) ^{ ()+1 } * k * . This expression is clearly divisible by , so the remaining task is to show that it is divisible by . Well show that ( * k * ) ^{ () } 1 is divisible by .

Since and * k * are relatively prime to , Eulers theorem tells us that ^{ () } and * k * ^{ () } are congruent to 1 (mod ). This implies that * k * ^{ () } is congruent to 1, and so * k * ^{ ()() } is also congruent to 1 (mod ). One of the basic properties of is that for relatively prime arguments and , () = ()() and so were done.

** Exercise ** : How much more can you generalize this? Does the base have to be the product of two distinct primes?