Question

Show that if p is an odd prime, then every divisor of the Mersenne number ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}$is of the form role="math" localid="1668665522353" $\mathbf{2}\mathit{k}\mathit{p}\mathbf{+}\mathbf{1}$where is a nonnegative integer [Hint: Use Fermat’s little theorem and Exercise 37 of Section4.3]

Short answer

By choosing a prime divisor ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}$and that the divisor is also of the form $\mathbf{2}\mathit{k}\mathit{p}\mathbf{+}\mathbf{1}$where $\mathit{k}$is a nonnegative integer, thus every divisor of the Mersenne number ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}$is of the form $\mathbf{2}\mathit{k}\mathit{p}\mathbf{+}\mathbf{1}$with $\mathit{k}$a nonnegative integer is proved.

Step-by-step solution

Definitions

FERMAT’S LITTLE THEOREM tells us that If $\mathit{p}$, is prime and $\mathit{a}$is an integer not divisible by $\mathit{p}$

Then ${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$

$\mathbf{a}\mathbf{\equiv }\mathbf{b}\mathbf{mod}\mathbf{m}$, If $\mathit{m}$divides $\mathit{a}\mathbf{-}\mathbf{b}$

To prove every divisor of the Mersenne number 2p−1 is of the form  2kp+1 with k a nonnegative integer is proved.

Let an odd prime be $\mathit{q}$and ${\mathbf{2}}^{\mathbf{p}\mathbf{-}\mathbf{1}}$as a divisor

By Fermat’s little theorem we know that,

${\mathbf{2}}^{\mathbf{q}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathit{q}$

$\mathbf{a}\mathbf{\equiv }\mathbf{b}\mathbf{mod}\mathbf{m}\mathbf{}$, If $\mathit{m}$divides $\mathbf{a}\mathbf{-}\mathbf{b}$then,

$\mathbf{q}\mathbf{\mid }{\mathbf{2}}^{\mathbf{q}\mathbf{-}\mathbf{1}}\mathbf{-}\mathbf{1}$

By using $\mathbf{gcd}\mathbf{}\left(2^a-1,2^b-1\right)\mathbf{=}{\mathbf{2}}^{\mathbf{g}\mathbf{ccd}\mathbf{}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}}\mathbf{-}\mathbf{1}$we get,

localid="1668664687688" $\mathbf{gcd}\mathbf{}\left(2^p-1,2^{q-1}-1\right)\mathbf{=}{\mathbf{2}}^{\mathbf{gcd}\mathbf{}\mathbf{(}\mathbf{p}\mathbf{,}\mathbf{q}\mathbf{-}\mathbf{1}\mathbf{)}}\mathbf{-}\mathbf{1}$

Here $\mathit{q}$is a divisor of ${\mathbf{2}}^{\mathbf{q}\mathbf{-}\mathbf{1}}\mathbf{-}\mathbf{1}$and ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}$. Therefore $\mathbf{gcd}\mathbf{}\left(2^p-1,2^{q-1}-1\right)\mathbf{>}\mathbf{1}$

Now since $\mathit{p}$is prime and $\mathit{p}$is divisible by $\mathbf{1}$and $\mathit{p}$only

Thus $\mathbf{gcd}\mathbf{}\mathbf{(}\mathit{p}\mathbf{,}\mathit{q}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{>}\mathbf{1}$is $\mathbf{gcd}\mathbf{}\mathbf{(}\mathit{p}\mathbf{,}\mathit{q}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{=}\mathit{p}$

$\mathit{p}\mathbf{\mid }\mathit{q}\mathbf{-}\mathbf{1}$

By the definition of divides there exists an integer $\mathit{m}$such that

$\mathit{q}\mathbf{-}\mathbf{1}\mathbf{=}\mathit{m}\mathit{p}$

Proof

Since q is odd andmis even.

Then there is an integer k we get,

$\begin{array}{c}\mathbf{m}\mathbf{=}\mathbf{2}\mathbf{k}\\ \mathbf{q}\mathbf{-}\mathbf{1}\mathbf{=}\mathbf{2}\mathbf{k}\mathbf{p}\end{array}$

Adding $\mathbf{1}$on both sides,

$\mathbf{q}\mathbf{=}\mathbf{2}\mathbf{kp}\mathbf{+}\mathbf{1}$

Thus this implied that all divisors of localid="1668665748321" ${\mathbf{2}}^{\mathbf{p}}\mathbf{-}\mathbf{1}\mathbf{}$are of the form $\mathbf{2}\mathit{k}\mathit{p}\mathbf{+}\mathbf{1}$

Thus proved.