Results 1 to 4 of 4

Math Help - Pigeon Hole Principle Help!

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Pigeon Hole Principle Help!

    I know I am supposed to PHP to figure this out, but I just can't do it.

    Let n be a natural number.

    Show that if e1, e2, ..., e11 are different positive integers, then there are two of them, call them ei, ej, such that (n^ei) - (n^ej) is divisible by 10. Any ideas? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Prove that 2 of the n^k mod10 evaluated for 11 different values of k will be the same number. Or think how many possible different remainders can exist mod10?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Now what would I do different if there are 6 different random integers rather than 11?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by jzellt View Post
    Now what would I do different if there are 6 different random integers rather than 11?
    Note that for a number to be divisible by 10, it should be divisible by 5 and 2.

    Now solve the problem separately for 5 and for 2, in the same way as before. That is ask yourself how many different remainders are possible mod5?

    For 2 it is trivial
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 04:24 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 07:22 PM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 03:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum