Exercise 2.4

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}}

If $a$ is a nonzero integer, then for $n > m$ show that $(a^{2^n} + 1, a^{2^m} + 1) = 1$ or $2$ depending on whether $a$ is odd or even.

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}
Let $d = a^{2^n} + 1 \wedge a^{2^m} + 1$. Then $d \mid  a^{2^n} + 1, d \mid  a^{2^m} + 1$. So
\begin{align*}
a^{2^n}  &\equiv -1 \pmod d,\
a^{2^m} &\equiv -1 \pmod d.
\end{align*}
As $n>m$, $2^{n-m}$ is even, so
$$-1 \equiv a^{2^n} = \left(a^{2^m}ight)^{2^{n-m}} \equiv (-1)^{2^{n-m}} \equiv 1 \pmod d.$$
$-1\equiv 1 \pmod d$, then $d \mid 2\ (d\geq 0)$. Thus $d =1$ or $d = 2$.

If $a$ is even, $a^{2^n} + 1$ is odd, so $d=1$.

If $a$ is odd, both $a^{2^n} + 1, a^{2^m} + 1$ are even, so $d=2$.
\end{proof}

Exercise 2.4

Answers

Comments

Exercise 2.4

Answers

Comments

Add answer