2

Prove that if a is a natural number, then there exists two unequal natural numbers k and l for which $$ a^k - a^l $$ is divisible by 10.

I'm strangely lost on this one. I understand the pigeonhole principle but I'm unsure how to apply it here. Any help is greatly aprpeciated.

beachtowel
  • 23
  • There are infinitely many natural numbers and there are only 10 possibilities for the last digit. And $\infty > 10$. – An Hoa Oct 22 '15 at 00:07

1 Answers1

2

HINT: Consider the possible last digits of powers of $a$. There are at most how many different possibilities?

Brian M. Scott
  • 616,228
  • There are 10. 0,1,....9. How do I use the pigeonhole principle to express this in a proof? – beachtowel Oct 22 '15 at 00:23
  • @beachtowel: Show that you must be able to find two different powers of $a$ with the same last digit. What happens when you take their difference? – Brian M. Scott Oct 22 '15 at 00:24
  • When you take their difference it becomes a number divisible by 10, right? I'm confused as to how to show the two powers of a with the same last digit. – beachtowel Oct 22 '15 at 00:27
  • @beachtowel: Yes to the first question. For the second, use the pigeonhole principle. There are at most ten possible last digits. Surely there are more than ten different powers of $a$ ... – Brian M. Scott Oct 22 '15 at 00:29
  • Ok, I think I get it. So, using the pigeon principle, I would put the powers of a (which is infinite) in let's say set A, and then the number of powers of a with the same last digit into let's say set B. Since |A| > |B|, it's not injective, and therefore, there exists some k and l that are divisible by 10. Is that accurate? – beachtowel Oct 22 '15 at 00:33
  • @beachtowel: You’re making it much too hard. Just look at the set ${a,a^2,a^3,\ldots,a^{11}}$; it has $11$ members, and there are at most $10$ possible last digits, so ... ? – Brian M. Scott Oct 22 '15 at 00:34
  • So using the pigeon hole example, there's 2 pigeons in one hole. Right? Sorry for the elaboration, I'm friend after a long day, please explain like I'm five. Haha. – beachtowel Oct 22 '15 at 00:39
  • @beachtowel: Think of each possible last digit as a hole. You have at most $10$ holes, but you have $11$ numbers in the set to put into those holes. Therefore? – Brian M. Scott Oct 22 '15 at 00:40
  • Therefore two numbers in one hole. I got that. It's really just that simple? – beachtowel Oct 22 '15 at 00:42
  • @beachtowel: It’s really just that simple, once you realize that you just need two powers of $a$ with the same last digit. – Brian M. Scott Oct 22 '15 at 00:42
  • Ok, thanks for your help. – beachtowel Oct 22 '15 at 00:43
  • @beachtowel: You’re welcome. – Brian M. Scott Oct 22 '15 at 00:44