Question

If a is a natural number, then there exist two unequal natural numbers k and l for which
\[a ^{j}-a ^{k}\] is divisible by 10.

My hint is to look at pigeonhole principle and equivalence classes.

I know I am essentially trying to prove the following, but I'm having trouble piecing things together to get my proof:

\[10|a ^{j}-a ^{k}\]


which of course is the same as

\[a ^{j}≡a ^{k}(mod\ 10)\]

Answer 1

typo in the question the unequal natural numbers are j and k, not k and l

Answer 2

yes, easily understandable :)

Answer 3

Let 0,1,2,3,4,5,6,7,8,9 be the canonical representatives of the equivalence classes of mod 10. E.g., [2] = { 2 + 10k | k \in Z }

Then given any natural number a, it may be written as
a = p + 10m, where p is a canonical representative.
Further, a^2 = p^2 mod 10 because a^2 = p^2 + 20mp + 100m^2. Now what class does p^2 belong to?

Look at what happens to each p, see how this behaves and you'll be able to construct your argument using a couple of different cases.

Answer 4

I'm still not seeing it. Apparently a lot of the class is having issues as well because the professor just sent us another hint, expanding on the hint we already had and seems to be tied in with what you are saying James, but I'm just not putting things together in my head.

Here's the hint he sent us:

"Think of the pigeon hole principle. To show the difference of two numbers to be divisible by ten is to show that they are congruent (mod 10) -- that they are in the same equivalence class mod 10. There are only 10 such equivalence classes -- [0], [1], ...[8], [9]. Surely you can fix a and consider enough powers of a that two of the powers must be in the same equivalence class."

Answer 5

Exactly. So given that a is in [1], p = 1. Hence
[a] = [1] ==> [a^2] = [1^2] = [1] = [a^3] = [a^4] = ....

[a] = [2] ==> [a^2] = [4], [a^3] = [8], [a^4] = [6], [a^5] = [2], and now the cycle repeats

[a] = [3] ==> [a^2] = [9], [a^3] = [1], [a^4] = [3], and now the cycle repeats

Find the cycles for each equivalence class

Answer 6

Thanks! I see it now.

Answer 7

@JamesJ and @ChrisS - are there any online tutorials on this subject area? it looks interesting and I would like to learn more about it.

Answer 8

I don't know about online tutorials, but the author of the book we use is a professor here at VCU and he has made it available online for free. Here's the url for it

http://www.people.vcu.edu/~rhammack/BookOfProof/index.html

Answer 9

thanks for that - it should keep me busy for quite a while I suspect :-)

Answer 10

just one more quick question to make sure I've totally got it. Once you cycle over and you subtract the first power from the power you are at when it cycles back to the same equivalence class, you get a number divisible by ten. That is in fact the proof of the statement.

Correct?