Prove that if a is a natural number then there exist two une

Prove that if a is a natural number, then there exist two unequal natural numbers k and ` for which a k a ` is divisible by 10.

Solution

Assume a is not divisible by 10. (otherwise the problem is trivial).
Define R(m) to be the remainder of a^m when divided by 10.
R can take on one of 9 possible values, namely, 1,2,...,9.
Now, consider R(1),R(2),......R(10). At least 2 of them must have the sames value (by the Pigeonhole Principle), say R(i) = R(j) ( j>i )
Then, a^j - a^i is divisible by 10