"

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?

"



    3           9