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]
$\displaystyle q \mid 2^p - 1 \ \Leftrightarrow \ 2^p \equiv 1 \ (\text{mod } q)$
Since $\displaystyle (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 $\displaystyle p \mid \phi (q)$, i.e. $\displaystyle p \mid q - 1$.
See if you can finish it off from there.
(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?