Bezout’s Identity states that for any natural numbers $a$ and $b$, there exist integers $x$ and $y$, such that

$$ \text{gcd}(a, b) = ax + by $$

Problem (42 Points Training, 2018)

Let $p$ be a prime, $p>2$. Prove that any prime divisor of the number $2^p-1$ has the form $2kp+1$, for some $k \in \mathbb{N}$.

Solution

Let $q$ be a prime divisor of $2^p-1$. Therefore $q$ is odd and

$$ 2^p \equiv 1 \hspace{0.05in} (\text{mod } q) $$

By Fermat’s Little Theorem

$$ 2^{q-1} \equiv 1 \hspace{0.05in} (\text{mod } q) $$

Since $p$ is prime, then $\text{gcd} (p,q-1)$ is either $1$ or $p$. If $\text{gcd} (p,q-1) =1$, by Bezout’s Lemma there exists some integers $x$ and $y$, such that

$$ 1=px+(q-1)y $$

 

and therefore

$$ 2^{1} \equiv 2^{px+(q-1)y} \equiv \left( 2^p \right)^x \cdot \left( 2^{q-1} \right)^y \equiv (1)^x \cdot (1)^y \equiv 1 \hspace{0.05in} (\text{mod } q) $$

which implies that $q | (2-1)$, i.e. $q|1$. Contradiction.

If $\text{gcd} (p,q-1) =p$, then $p|(q-1)$. Since $p$ is odd and $q-1$ is even, then $2p | (q-1)$ and therefore $q=2kp+1$, for some $k \in \mathbb{N}$.

---