Results 1 to 8 of 8

Math Help - p,q odd primes & q|(2^p)-1 => q=2pk+1

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    p,q odd primes & q|(2^p)-1 => q=2pk+1

    Prove that if p and q are odd primes and q divides (2^p)-1, then q=2pk+1 for some integer k.

    I can't find any clue on this one...
    Any help is appreciated!


    [also under discussion in math links forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    q \mid 2^p - 1 \ \Leftrightarrow \ 2^p \equiv 1 \ (\text{mod } q)

    Since (2,q) = 1, then the order of 2 (mod q) is a divisor of p (why?) and so, the order is either 1 or p. It must be p.

    So since the order of 2 is p, we know p \mid \phi (q), i.e. p \mid q - 1.

    See if you can finish it off from there.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by o_O View Post
    q \mid 2^p - 1 \ \Leftrightarrow \ 2^p \equiv 1 \ (\text{mod } q)

    Since (2,q) = 1, then the order of 2 (mod q) is a divisor of p (why?) and so, the order is either 1 or p. It must be p.

    So since the order of 2 is p, we know p \mid \phi (q), i.e. p \mid q - 1.

    See if you can finish it off from there.
    So we have q-1=pz for some integer z. q-1 is even.

    How can we prove that 2p|(q-1) ?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Start from here: q - 1 = zp, \ z \in \mathbb{Z}

    We know that p and q are odd. What does this tell you about z?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by o_O View Post
    Start from here: q - 1 = zp, \ z \in \mathbb{Z}

    We know that p and q are odd. What does this tell you about z?
    OK, I got it.
    z must be even; z=2k for some integer k.
    So we have our result: q=2pk+1 for some integer k.

    Is it true that ANY divisor(not necessarily prime) of (2^p)-1 is also of the form 2pk+1? Why or why not?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Well, consider the prime power decomposition of 2^p - 1.

    Through what we've just proven, what can be said about these primes? And hence what about the product between any of these primes?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by o_O View Post
    Well, consider the prime power decomposition of 2^p - 1.

    Through what we've just proven, what can be said about these primes? And hence what about the product between any of these primes?
    (2^p)-1 is odd, so 2 is not a factor in the prime factorization of (2^p)-1. So every prime factor is odd and of the form 2pk+1.

    I can also show that a product of two factors of the form 2pk+1 is of the same form (i.e. the product is of the form 2pm+1 for some integer m).

    So by induction, we can say that ANY divisor(not necessarily prime) of (2^p)-1 is also of the form 2pk+1? Am I right?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Quote Originally Posted by kingwinner View Post
    Am I right?
    Why the doubt?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 2nd 2010, 11:18 AM
  2. For what primes p...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 29th 2010, 07:08 AM
  3. primes...
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 28th 2010, 06:53 PM
  4. n^2 + n + 41 and primes
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 26th 2010, 09:13 AM
  5. About Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 17th 2009, 06:44 AM

Search Tags


/mathhelpforum @mathhelpforum