Thread: Pigeonhole principle question

Any power of 2 is even and any power of 5 is a multiple of 5. Let p be a prime with p not equal to 2,5. show that among the numbers p^1,p^2,p^3,....,p^40 at least one of them has 01 as its last two digits.

Focus on the numbers mod 100 (i.e., only the last 2 digits). There are 100 total, but you can remove 50 of these since they are even, and remove 10 because they end in 5). Your powers of primes will never end in these values. The remaining 40 roughly form a group in that they will multiply into themselves. Your 40 powers either cover this group of 40 evenly, so one of them will cover 01, or if there is a pattern, you can find a power acting as the identity, i.e., 01.

Originally Posted by sbankica

Any power of 2 is even and any power of 5 is a multiple of 5. Let p be a prime with p not equal to 2,5. show that among the numbers p^1,p^2,p^3,....,p^40 at least one of them has 01 as its last two digits.

Consider modulo 100. Since p is not equal to 2 or 5, there are 100 - (100/2) - (100/5) + (100/10) = 40 possible congruence classes for the powers of p.

If any is congruent to 1 modulo 100 we are done.

If not, then there are 39 possible congruence classes and 40 powers of p, so one of the classes must contain at least two powers of p, say . Then .