Question

Show that if$2^m+1$is an odd prime, then $m=2^n$ for some nonnegative integer $n$. [Hint: First show that the polynomial identity $x^m+1=\left(x^k+1\right)\left(x^{k(t-1)}-x^{k(t-2)}+\dots -x^k+1\right)$ holds, where$m=kt$and$t$ is odd.]

Short answer

If $2^m+1$is an odd prime, then $m=2^n$for some nonnegative integer$n$.

Step-by-step solution

Step 1

DEFINITIONS

An integer $p$is called prime if $p>1$and if the only positive factors of $p$ are 1 and $p$.

$n$ is even if and only if $n$is divisible by 2 if and only if there exists an integer $k$ such that $n=2k$

Division algorithm Let$n$be an integer and$d$a positive integer. Then there are unique integers$q$and$r$with$0\le r<d$such that$n=dq+r$

$q$ is called the quotient and $r$ is called the remainder

$q=n$ div $d$

$r=n$ mod $d$

$a$ is congruent to $b$ modulo if divides $a-b$.Notation: $a\equiv b\left(modm\right)$ .

Step 2

SOLUTION

To proof: If $2^m+1$ is an odd prime, then $m=2^n$for some nonnegative integer $n$.

PROOF

Let $2^m+1$be an odd prime.

Since $2\equiv -1\left(\mathrm{mod}3\right),2^{\mathrm{m}}\equiv {\left(-1\right)}^{\mathrm{m}}\left(\mathrm{mod}3\right)$, and thus $2^m+1\equiv {\left(-1\right)}^m+1\left(\mathrm{mod}3\right)$. Since ${\left(-1\right)}^m=1$ when $m$ even and ${\left(-1\right)}^m=1$ when $m$ odd, role="math" localid="1668497870250" $2^m+1\equiv 2\left(\mathrm{mod}3\right)$ when $m$even and role="math" localid="1668497862840" $2^m+1\equiv 0\left(\mathrm{mod}3\right)$when $m$odd. However, $2^m+1\equiv 0\left(\mathrm{mod}3\right)$ is impossible as 3 would then divide $2^m+1$(which is in contradiction with the fact that $2^m+1$is prime). Thus we then require that $2^m+1\equiv 2\left(\mathrm{mod}3\right)$ with $m$ even.

$2^m+1\equiv 2\left(\mathrm{mod}3\right)$with $m$even.

Since $m$ is even, there exists an integer $k$ such that $m=2k$.

When $k=1$, then the proof is finished. When odd, then:

$$\begin{gathered} 2^m+1=2^{2k}+1 \\ =\left(2^2+1\right)\left({\left(2^2\right)}^{m_1-1}-{\left(2^2\right)}^{m_2-1}+\dots -2^2+1\right) \\ =5\left({\left(2^2\right)}^{m_4-1}-{\left(2^2\right)}^{m_2-1}+\dots -2^2+1\right) \end{gathered}$$

Step 3

When$k$odd with $k\ne 1$ , then we thus note that 5 would divide $2^m+1$, which is in contradiction with$2^m+1$being prime and thus$k$needs to be even.

Since$k$is even, there exists an integer$k_1$such that$k=2k_1$.

$m=2k=2\left(2k_1\right)=2^2{k}_1$.

When $k_1=1$, then the proof is finished. $k_1$cannot be odd and greater than 1 (as then $2^{k_1}+1$divides $2m+1$) and thus we then require $k_1$ even.

Repeating this procedure until we obtain a $k_{n}i=1$ (which we need to obtain at some point as $k_i$can never be odd with $k_i>1$ and becomes smaller and smaller as $i$ increases), we then obtain $m=2^n{k}_n=2^n\left(1\right)=2^n$ for some nonnegative integer $n$.