Exercise 5.11

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Suppose that $p \equiv 3 \pmod 4$, and that $q = 2p+1$ is also prime. Prove that $2^p -1$ is not prime. (Hint : Use the quadratic character of 2 to show that $q\mid 2^p-1$) One must assume that $p>3$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow} \def\gcro{\mbox{[\hspace{-.15em}[}} \def\dcro{\mbox{]\hspace{-.15em}]}} ewcommand{\D}{\mathrm{d}} ewcommand{\Q}{\mathbb{Q}} ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} ewcommand{\C}{\mathbb{C}} ewcommand{\F}{\mathbb{F}} ewcommand{ e}{\,\mathrm{Re}\,} ewcommand{\ord}{\mathrm{ord}} ewcommand{ }{\mathrm{N}} ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}} \begin{proof} The result is false if $p=3$, so we must suppose $p>3$. $p=4k+3$ for an integer $k$, so $q = 2p+1 = 8k+7 \equiv -1 \pmod 8$. Thus $$\legendre{2}{q} = (-1)^{(q^2-1)/8} = 1.$$ Therefore $2^{(q-1)/2} \equiv 1 \pmod q$, $2^p \equiv 1 \pmod q$, so $q \mid 2^p-1$. Moreover, as $p>3$, $q=2p+1<2^p-1$ (indeed $(2p+1<2^p-1 \iff 2p < 2^p - 2 \iff p +1< 2^{p-1} $. $4+1 < 2^{4-1}$ and for all $k\geq 4$, $k+1 < 2^{k -1}$ implies $k+2 < 2^{k-1} + 1\leq 2^k$, so by induction $k+1 < 2^{k -1}$ for all $k>3$). Thus $q \mid 2^p-1$ with $1 < q < 2^p-1$, and so $2^p - 1$ is composite. Conclusion: if $p \equiv 3 \pmod 4, p>3$ is prime, and $q = 2p+1$ is also prime, then $2^p - 1$ is not a prime. For instance, the Mersenne's number $2^{11} - 1 =2047$ is not a prime : $2047 = 23 imes 89$. \end{proof}

Exercise 5.11

Answers

Comments

Exercise 5.11

Answers

Comments

Add answer