Results 1 to 5 of 5

Math Help - Pigeonhole problem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    7

    Pigeonhole problem

    Prove that there exists a positive integer n so that 44^n — 1 is divisible
    by 7.
    Last edited by dajaka; October 18th 2008 at 02:40 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    There's no real need for a pigenhole principle here (look for little Fermat's theorem), but let's do it your way.
    Consider the eight numbers 44^0,44^1, 44^2,\ldots,44^7. There are only 7 possible remainders in the division of these numbers by 7 (namely 0, 1,..., 6), hence at least two of these numbers have the same remainder modulo 7: this results from a pigeonhole principle. Let's say it is 44^m and [tex]44^n[/Math], [tex]n<m[/Math]. Then, for some a,a',r, 44^m = 7a + r and 44^n=7a' + r, hence 44^m-44^n=7(a-a'). Because 44^m-44^n=44^n(44^{m-n}-1), this gives 44^n(44^{m-n}-1)=7(a-a'), so that 7 divides 44^n(44^{m-n}-1). In addition, 7 and 44 are relatively prime, hence we deduce that 7 divides 44^{m-n}-1. And m-n\geq 1. We are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    7
    thank you very much
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by dajaka View Post
    SOLVED, THANX
    It's not good form to delete questions. Now other members can't view it at a later date and perhaps learn something.

    @Laurent: A good reason to always quote the question when replying .......
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    7
    ok sorry
    here is the problem again...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 03:46 PM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 11th 2010, 01:33 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 04:31 PM
  4. pigeonhole problem ... ASAP please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 29th 2008, 11:03 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum