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

1. ## 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]

2. $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.

3. Originally Posted by o_O
$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!

4. 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$?

5. Originally Posted by o_O
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!

6. 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?

7. Originally Posted by o_O
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?

8. Originally Posted by kingwinner
Am I right?
Why the doubt?