Results 1 to 3 of 3

Math Help - Pigeonhole principle question

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Exclamation 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by sbankica View Post
    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 p^1, p^2, \dots , p^{40} 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 p^n \text { where } 1 \leq n \leq 40 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 p^n \equiv p^m \pmod{100}. Then p^{n-m} \equiv 1 \pmod{100}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeonhole Principle Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2010, 11:50 AM
  2. pigeonhole principle
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 24th 2009, 12:46 PM
  3. Replies: 2
    Last Post: February 16th 2009, 07:30 AM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2008, 09:09 AM
  5. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum