Ireland_Rosen_Chapters_4_5_6.tex

%&LaTeX
\documentclass[11pt,a4paper]{article}
\usepackage[frenchb,english]{babel}
\usepackage[applemac]{inputenc}
\usepackage[OT1]{fontenc}
\usepackage[]{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{yfonts}
%\input{8bitdefs}

% marges
\topmargin 10pt
\headsep 10pt
\headheight 10pt
\marginparwidth 30pt
\oddsidemargin 40pt
\evensidemargin 40pt
\footskip 30pt
\textheight 670pt
\textwidth 420pt

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

\newcommand{\D}{\mathrm{d}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}



\title{Solutions to Ireland, Rosen ``A Classical Introduction to Modern Number Theory''}
\author{Richard Ganaye}
\begin{document}

\maketitle

{\large \bf Chapter 4}

\paragraph{Ex. 4.1}

{\it Show that $2$ is a primitive root modulo $29$.
}

\begin{proof}
Let $p=29$. The integer $p$ is prime and $p-1 = 2^2\times 7$.

Note that

$2^4 = 16 \not \equiv1\pmod {29},$

$2^{14} =  4 ^7 =4 \times 16^2 = 64\times 256 \equiv 6 \times (-34)=-204\equiv 86=3\times 29 -1 \equiv -1\pmod{29}$.

$2^{28} \equiv 1\pmod {29}$ and $2^d \not \equiv 1$ if $d \mid 28, d < 28$, hence 2 is a primitive element modulo 29.
\end{proof}

\paragraph{Ex. 4.2}

{\it Compute all primitive roots for $p = 11, 13, 17$, and $19$.
}

\begin{proof}
$\bullet$ $p=11$. Then $p-1 = 10 = 2\times 5$.

Since $2^2 = 4 \not \equiv 1 \pmod {11}$, and $2^5 = 32 \equiv -1 \not \equiv 1 \pmod{11}$, $2$ is a primitive element modulo $11$.

The other primitive elements modulo $11$ are congruent to the powers $2^i, i\wedge 10 = 1, 1\leq i <10$, namely $2,2^3,2^7,2^9$.

$2^7 \equiv 7 \pmod {11},2^9 \equiv 6 \pmod {11}$, so

$ \{\overline{2}, \overline{8}, \overline{7}, \overline{6}\}$ is the set of the generators of $U(\Z/11\Z)$.

Similarly :

$\bullet$ $p=13$ : $\{2,6,11,7\}$ is the set of the generators of $U(\Z/13\Z)$.

$\bullet$ $p=17$ : $\{3, 10, 5, 11, 14, 7, 12, 6\}$ is the set of the generators of $U(\Z/17\Z)$.

$\bullet$ $p=19$ : $\{2, 13, 14, 15, 3, 10\}$ is the set of the generators of $U(\Z/19\Z)$.

I obtain these results with the direct orders in S.A.G.E. :
\begin{verbatim}
p = 19; Fp = GF(p); a = Fp.multiplicative_generator()
print([a^k for k in range(1,p) if gcd(k,p-1) == 1])
\end{verbatim}
\end{proof}

\paragraph{Ex. 4.3}

{\it Suppose that $a$ is a primitive root modulo $p^n$, $p$ an odd prime. Show that $a$ is a primitive root modulo $p$.
}

\begin{proof}
Suppose that $a$ is a primitive root modulo $p^n$. Then $\overline{a}$ is a generator of $U(\Z/p^n\Z)$.

If $a$ was not a primitive root modulo $p$, $\overline{a}$ is not a generator of $U(\Z/p\Z)$, so there exists $b \in \Z, b \wedge p = 1$ such that $a^k \not \equiv b \pmod p$ for all $k\in \Z$. A fortiori $a^k \not \equiv b \pmod {p^n}$, and $b \wedge p^n = 1$, so $\overline{b} \in U(\Z/p^n\Z)$ and $\overline{b} \not \in \langle \overline{a} \rangle$ in $U(\Z/p^n\Z)$, in contradiction with the hypothesis. So $a$ is a primitive root modulo $p$.

(The reasoning on the orders of $a$, modulo $p$ and modulo $p^n$, is possible, but not so easy.)
\end{proof}

\paragraph{Ex. 4.4}

{\it 
Consider a prime $p$ of the form $4t + 1$. Show that $a$ is a primitive root modulo $p$ iff $-a$ is a primitive root modulo $p$.
}

\begin{proof} 
Solution 1.

Suppose that $a$ is a primitive root modulo $p$.
As $p-1$ is even, $(-a)^{p-1} = a^{p-1} \equiv 1 \pmod p$.

If $(-a)^n \equiv 1 \pmod p$, with $n \in \N$, then $a^n \equiv (-1)^n \pmod p$. 

Therefore $a^{2n} \equiv 1 \pmod p$. As $a$ is a primitive root modulo $p$, $p-1 \mid 2n$, $2t \mid n$, thus $n$ is even. 

Since $(-1)n = 1$, $a^n \equiv 1 \pmod p$,  and  $p-1 \mid n$. So the least $n\in \N^*$ such that $(-a)^n \equiv 1 \pmod p$ is $p-1$: the order of $-a$ modulo $p$ is $p-1$, $-a$ is a primitive root modulo $p$.

Conversely, if $-a$ is a primitive root modulo $p$, we apply the previous  result at $-a$ to to obtain that $-(-a) = a$ is a primitive root.
\bigskip

Solution 2.

Let $p-1 = 2^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ the decomposition of $p-1$ in prime factors. 

 As $p_i$ is odd for $i=1,2,\cdots k$, $(p-1)/p_i$ is even, and $a$ is primitive, so 
 \begin{align*}
& (-a)^{(p-1)/p_i} = a^{(p-1)/p_i} \not \equiv 1 \pmod p,\\
&(-a)^{(p-1)/2}  = (-a)^{2k} = a^{2k} = a^{(p-1)/2} \not \equiv 1 \pmod p.
 \end{align*}
 So the order of $a$ is $p-1$ modulo $p$ (see Ex. 4.8) : $a$ is a primitive element modulo $p$.
\end{proof}

\paragraph{Ex. 4.5}

{\it Consider a prime $p$ of the form $4t + 3$. Show that $a$ is a primitive root modulo $p$ iff $-a$ has order $(p - 1)/2$.
}

\begin{proof}
Let $a$ a primitive root modulo $p$. 

Then $a^{p-1} \equiv 1 \pmod p$, $p \mid (a^{(p-1)/2} - 1)(a^{(p-1)/2} + 1)$, thus $p \mid a^{(p-1)/2} - 1$ or $p \mid a^{(p-1)/2} + 1$. Since $a$ is a primitive root modulo $p$, $a^{(p-1)/2} \not \equiv 1 \pmod p$, thus 
$$a^{(p-1)/2} \equiv -1 \pmod p.$$

Hence $(-a)^{(p-1)/2} = (-1)^{2t+1} a^{(p-1)/2}  \equiv (-1)\times (-1) =1 \pmod p$.

Suppose that  $(-a)^n \equiv 1 \pmod p$, with $n \in \N$.


Then $a^{2n} = (-a)^{2n} \equiv 1 \pmod p$, so $p-1 \mid 2n, \frac{p-1}{2} \mid n$.

This proves that $-a$ has order $(p-1)/2$ modulo $p$.

\bigskip

Conversely, suppose that $-a$ has order $(p-1)/2 = 2t+1$ modulo $p$. Let $2,p_1,\ldots p_k$ the prime factors of $p-1$, where the primes $p_i$ are odd.

$a^{(p-1)/2} = a^{2t+1} = -(-a)^{2t+1} = -(-a)^{(p-1)/2} \equiv - 1$, so $a^{(p-1)/2} \not \equiv 1 \pmod 2$.

As $p-1$ is even, $(p-1)/p_i$ is even, thus

$a^{(p-1)/p_i} = (-a)^{(p-1)/p_i} \not \equiv 1 \pmod p$ (since $-a$ has order $p-1)$.

So the order of $a$ is $p-1$ (see Ex. 4.8) : $a$ is a primitive root modulo $p$.
\end{proof}


\paragraph{Ex. 4.6}

{\it If $p = 2^{2^n} + 1$ is a Fermat prime, show that $3$ is a primitive root modulo $p$.
}

\begin{proof}

Solution 1 (with quadratic reciprocity).

Write $p = 2^k + 1$, with $k = 2^n$.

We suppose that $n>0$, so $k\geq 2, p \geq 5$. As $p$ is prime, $3^{p-1} \equiv 1 \pmod p$. 

In other words, $3^{2^k} \equiv 1 \pmod p$: the order of $3$ is a divisor of $2^k$, a power of $2$.

$3$ has order $2^k$ modulo $p$ iff $3^{2^{k-1}} \not \equiv 1 \pmod p$. As $\left (3^{2^{k-1}} \right)^2 \equiv 1 \pmod p$, where $p$ is prime, this is equivalent to $3^{2^{k-1}}  \equiv -1 \pmod p$, which remains to prove.

$3^{2^{k-1}} = 3^{(p-1)/2} \equiv \legendre{3}{p} \pmod p$.

Since $n\geq 1$, $k\geq 2$, thus $2^{k-1}$ is even.
By the law of quadratic reciprocity,
$$\legendre{3}{p} \legendre{p}{3} = (-1)^{(p-1)/2} = (-1)^{2^{k-1}} = 1.$$
Therefore $\legendre{3}{p} = \legendre{p}{3}$, and
\begin{align*}
p = 2^{2^n}+1 &\equiv (-1)^{2^n} + 1 \pmod 3\\
&\equiv 2 \equiv -1 \pmod 3,
\end{align*}
so $\legendre{3}{p} = \legendre {p}{3} = -1$, that is to say
$$3^{2^{k-1}}  \equiv -1 \pmod p.$$
The order of $3$ modulo $p = 2^{2^n} + 1$ is $p-1 = 2^{2^n}$, i.e. $3$ is a primitive root modulo $p$.

(On the other hand, if the order of $3$ modulo $p$ is $p-1$, then $p$ is prime, so
$$ F_n = 2^{2^n} + 1 \ \mathrm{is}\ \mathrm{prime}\ \iff 3^{(F_n-1)/2} = 3^{2^{2^n - 1}} \equiv -1 \pmod {F_n}.)$$

\bigskip

Solution 2 (without quadratic reciprocity, with the hint of  chapter 4).

As above, if we suppose that $3$ is not a primitive root modulo $p$, then 
$$3^{2^{k-1}}  \equiv 1 \pmod p,$$
where $k=2^n \geq 2$, and $p = 2^k+1$.

Therefore $(-3)^{(p-1)/2} = 3^{2^{k-1}}  \equiv 1 \pmod p$, thus $-3$ is a square modulo $p$. So there is some $a \in \Z$ such that $-3 \equiv a^2 \pmod p$. 

As $2\wedge p = 1$, $2$ has an inverse modulo $p$, so there exists $u \in \Z $ such that $2u \equiv -1+a \pmod p$ ($\overline{u}$ is similar to $\omega = \frac{-1 + i \sqrt{3}}{2} \in \C$). Then
\begin{align*}
8u^3 &\equiv (-1+a)^3\\
&\equiv -1+3a - 3a^2 +a^3\\
&\equiv -1 +3a + 9 -3a\\
&\equiv 8 \pmod p
\end{align*}
As $p\wedge 2 = p \wedge 8 = 1, u^3 \equiv 1 \pmod p$. Moreover, if $u \equiv 1 \pmod 3$, then $a \equiv 3 \pmod p$, $-3 \equiv 9 \pmod p, p\mid 12$, so $p = 2$ or $p=3$, in contradiction with $p\geq 5$. So the order of $u$ modulo $p$ is $3$ : $(\Z/p\Z)^*$ contains an element $\overline{u}$ of order $3$. So $3 \mid p-1$, $p\equiv 1 \pmod 3$, but $p \equiv (-1)^{2^n} + 1 \equiv 2 \equiv -1 \pmod 3$ : this is a contradiction, so $3$ is a primitive root modulo $p = 2^{2^n} +1$.
\end{proof}

\paragraph{Ex. 4.7}

{\it Suppose that $p$ is a prime of the form $8t + 3$ and that $q = (p -1)/2$ is also a prime.  Show that $2$ is a primitive root modulo $p$.
}

\begin{proof}
The first examples of such couples $(q,p)$ are $(5,11), (29,59) ,(41,83) ,(53,107) ,(89,179)$.

$p = 2q+1 = 8t+3$ and $p,q$ are prime numbers.

From Fermat's little theorem, $2^{p-1} \equiv 1 \pmod p$, so $2^{2q} \equiv 1 \pmod p$.

The order of $2$ modulo $p$ divides $2q$ : to prove that the order of $2$ is $2q = p-1$, it is sufficient to prove that
$$2^2 \not \equiv 1 \pmod p, \quad 2^q \not \equiv 1 \pmod p.$$

If $2^2 \equiv 1 \pmod p$, then $p \mid 3$, $p=3$ and $q = 1$ : $q$ is not a prime, so $2^2 \not \equiv 1 \pmod p$.

If $2^q  = 2^{(p-1)/2} \equiv 1 \pmod p$, then $2$ is a square modulo $p$ (prop. 4.2.1), there exists $a \in \Z$ such that $2\equiv a^2 \pmod p$.


From the complementary case of the law of quadratic reciprocity (see next chapter, prop. 5.1.3),  $2$ is a square modulo $p$ iff 
$$1 = \legendre{2}{p} = (-1)^{(p^2-1)/8}.$$
Yet  $p\equiv 3 \pmod 8$, so $p^2 \equiv 9 \pmod {16}$, $\legendre{2}{p} = (-1)^{(p^2-1)/8} = -1$, so $2$ is not a square modulo $p$. This is a contradiction, so $2^q\not \equiv 1 \pmod p$ : $2$ is a primitive root modulo $p$.
\end{proof}

\paragraph{Ex. 4.8}

{\it  Let $p$ be an odd prime. Show that $a$ is a primitive root modulo $p$ iff $a^{(p-1)/q} \not \equiv 1 \pmod p$ for all prime divisors $q$ of $p - 1$.
}

\begin{proof}
$\bullet$ If $a$ is a primitive root, then $a^k \not \equiv 1$ for all $k, 1\leq k < p-1$, so $a^{(p-1)/q} \not \equiv 1 \pmod p$ for all prime divisors $q$ of $p - 1$.

$\bullet$ In the other direction, suppose $a^{(p-1)/q} \not \equiv 1 \pmod p$ for all prime divisors $q$ of $p - 1$.

Let $\delta$ the order of $a$, and $p-1 = q_1^{a_1}q_2^{a_2}\cdots q_k^{a_k}$ the decomposition of $p-1$ in prime factors. As $\delta \mid p-1, \delta = q_1^{b_1}q_2^{b_2}\cdots q_k^{b_k}$, with $b_i \leq a_i, i=1,2,\ldots,k$. If $b_i < a_i$ for some index $i$, then $\delta \mid (p-1)/q_i$, so $a^{(p-1)/q_i} \equiv 1 \pmod p$, which is in contradiction with the hypothesis. Thus $b_i = a_i$ for all $i$, and $\delta = q-1$: $a$ is a primitive root modulo $p$.
\end{proof}

\paragraph{Ex. 4.9}

{\it Show that the product of all the primitive roots modulo $p$ is congruent to $(-1)^{\phi(p-1)}$ modulo $p$.
}

\begin{proof} Here we suppose $p$ prime, $p>2$. Let $g$ be a primitive root modulo $p$. $U(\Z/p\Z)$ is cyclic, generated by $\overline{g}$:
$$U(\Z/p\Z) = \{\overline{1},\overline{g}, \overline{g}^2, \ldots,\overline{g}^{p-2}\},\qquad \overline{g}^{p-1} = \overline{1}.$$
$\overline{g}^k$ is a primitive element iff $k \wedge (p-1) = 1$, therefore the product of primitive elements in $U(\Z/p\Z)$ is
$$\overline{P} = \prod_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}} \overline{g}^k.$$
thus $\overline{P} = \overline{g}^S$, where $S = \sum\limits_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}}  k$.

From Ex. 2.22, we know that for $n\geq 2$,
$$\sum_{\overset{k\wedge n = 1}{ 1\leq k < n}}  k = \frac{1}{2} n \phi(n).$$
So $S = \sum\limits_{\overset{k\wedge (p-1) = 1}{ 1\leq k < p-1}}  k = \frac{1}{2} (p-1) \phi(p-1)$.

As $p>2$, $p-1$ is even. $(\overline{g}^{(p-1)/2})^2 = \overline{g}^{p-1} = \overline{1}$, and $\overline{g}^{(p-1)/2} \ne \overline{1}$. As $\Z/p\Z$ is a field, $\overline{g}^{(p-1)/2} = -\overline{1}$.

Thus $\overline{P} = (-\overline{1})^{\phi(p-1)}$, and the product $P$ of all the primitive roots modulo $p$ is such that
$$P \equiv  (-1)^{\phi(p-1)} \pmod p.$$
\end{proof}

\paragraph{Ex. 4.10}

{\it Show that the sum of all the primitive roots modulo $p$ is congruent to $\mu(p-1)$ modulo $p$.
}


\begin{proof}
Notation: $\F_p=\Z/p\Z$ is the field with $p$ elements, $\vert x \vert$ the multiplicative order of an element $x \in \F_p^*$, $\N^* = \{1,2,3,\ldots\}$.

Let
$$
\psi : 
\left\{
\begin{array}{ccc}
\N^*  & \to   &  \F_p \\
 n  &\mapsto   &  \psi(n) = \sum\limits_{d \in \F_p^*,\vert d \vert =n} d,   
\end{array}
\right.
$$
so that $\psi(n)$ is the sum of the elements  with order $n$ in $\F_p^*$. So $\psi(n) = 0$ if $n \nmid p-1$, and $S = \psi(p-1)$ is the sought sum of all the primitive roots modulo $p$.

We compute for all $n \in \N^*$
$$f(n) = \sum\limits_{d \mid n} \psi(d).$$

$f(n)$ is the sum of elements whose order divides $n$, in other worlds the sum of the roots of $x^n - 1$. This sum is, up to the sign, the coefficient of $x^{n-1}$, so is null, except in the case $n=1$, where the sum of the unique root $1$ of $x-1$ is $1$. So
$$f(1) = 1, \qquad \forall n > 1,f(n) = 0,$$
($f  = \chi_{\{1\}}$ is the characteristic function of $\{1\}$).

From the M\"{o}bius inversion formula, for all $n \in \N^*, \psi(n) = \sum_{d\mid m} \mu\left (\frac{n}{d}\right) f(d)$, so
$$\psi(p-1) =  \sum_{d\mid p-1} \mu\left (\frac{p-1}{d}\right) f(d) = \mu(p-1).$$

Conclusion : $$S = \sum\limits_{d \in \F_p^*,\vert d \vert =p-1} d = \mu(p-1) :$$ 
the sum of all the primitive roots modulo $p$ is congruent to $\mu(p-1)$ modulo $p$.
\end{proof}

\paragraph{Ex. 4.11}

{\it Prove that $1^k + 2^k + . . . + (p-1)^k \equiv 0 \pmod p$ if $p-1 \nmid k$, and $ -1 \pmod p$ if $p-1 \mid k$.
}

\begin{proof}
Let $S_k = 1^k+2^k+\cdots+(p-1)^k$.

Let $g$ a primitive root modulo $p$ : $\overline{g}$ a generator of $\F_p^*$.

As $(\overline{1},\overline{g},\overline{g}^{2}, \ldots, \overline{g}^{p-2}) $ is a permutation of $ (\overline{1},\overline{2}, \ldots,\overline{p-1})$,
\begin{align*}
\overline{S_k} &= \overline{1}^k + \overline{2}^k+\cdots+ \overline{p-1}^k\\
&= \sum_{i=0}^{p-2} \overline{g}^{ki} =
\left\{
\begin{array}{ccc}
\overline{ p-1} = -\overline{1} &  \mathrm{if} &  p-1 \mid k  \\
 \frac{ \overline{g}^{(p-1)k} -1}{ \overline{g}^k -1} = \overline{0}&  \mathrm{if}  &   p-1 \nmid k
\end{array}
\right.
\end{align*}
since $p-1 \mid k \iff \overline{g}^k = \overline{1}$.

Conclusion :
\begin{align*}
1^k+2^k+\cdots+(p-1)^k&\equiv 0 \pmod p\ \mathrm{if} \ p-1 \nmid k,\\
1^k+2^k+\cdots+(p-1)^k&\equiv -1 \pmod p\ \mathrm{if} \ p-1 \mid k.\\
\end{align*}
\end{proof}

\paragraph{Ex. 4.12}

{\it Use the existence of a primitive root to give another proof of Wilson's theorem $(p - 1)! \equiv -1  \pmod p$.
}

\begin{proof} As the result is trivial if $p=2$, we suppose that $p$ is an odd prime. 

Let $g$ be a primitive root modulo $p$. Then $\overline{g}$ is a generator of $\F_p^*$.

As $(\overline{g}^{(p-1)/2}) ^2 = \overline{g}^{p-1} = \overline{1}$, and $\overline{g}^{(p-1)/2} \neq 1$ in the field $\F_p^*$,  then $\overline{g}^{(p-1)/2} = -1$, and $(\overline{1},\overline{g},\overline{g}^{2}, \ldots, \overline{g}^{p-2}) $ is a permutation of $ (\overline{1},\overline{2}, \ldots,\overline{p-1})$, thus
\begin{align*}
\overline{(p-1)!} &= \prod_{k=0}^{p-2} \overline{g}^k\\
&= \overline{g}^{\sum_{k=0}^{p-2} k}\\
&=\overline{g}^{(p-2)(p-1)/2}\\
&=\left(\overline{g}^{(p-1)/2}\right)^{p-2}\\
&=(-\overline{1})^{p-2}\\
&= - 1.
\end{align*}
Hence $(p-1)! \equiv -1\pmod p$ for each prime $p$.
\end{proof}

\paragraph{Ex. 4.13}

{\it Let $G$ be a finite cyclic group and $g \in G$ a generator. Show that all the other generators are of the form $g^k$, where $(k, n) = 1$, $n$ being the order of $G$.
}

\begin{proof}
Suppose $G = \langle g \rangle$, with $\mathrm{Card}\, G = n$, so that the order of $g$ is $n$.

Let $x$ be another generator of $G$, then $x= g^k$, and $g = x^l, \ k,l \in \Z$, so $g = g^{kl}, g^{kl-1} = e : n \mid kl-1$, then $kl - 1 = qn, q\in \Z$, so $n\wedge k = 1$.

Conversely, if $u\wedge k = 1$, there exist $u,v \in \Z$ such that $un+vk=1$, so $g = g^{un+vk} = (g^n)^u(g^k)^v = x^v \in \langle x \rangle$, so $G \subset \langle x \rangle$, $G = \langle x \rangle$, i.e. $x$ is a generator of $G$.

Conclusion: if $g$ is a generator of $G$, all the other generators are the elements $g^k$, where $k \wedge n  = 1$, $n = \vert G \vert$.
\end{proof}

\paragraph{Ex. 4.14}

{\it Let $A$ be a finite abelian group and $a, b \in A$ elements of order $m$ and $n$, respectively.  If $(m, n) = 1$, prove that $ab$ has order $mn$.
}

\begin{proof}
Suppose $\vert a \vert = m, \vert b \vert = n, m\wedge n = 1$.

$\bullet$ If $(ab)^k = e$, then $a^k= b^{-k}$, so $a^{kn} = b^{-kn} = (b^n)^{-k} = e$, thus $m\mid kn$, with $m\wedge n = 1$, therefore $m \mid k$.

Similarly, $ b^{km} =a^{-km} = (a^m)^{-k} = e$, thus $n \mid km, n \wedge m = 1$ : $n \mid k$. 

As $n \mid k, m \mid k, n \wedge m = 1$, we conclude $nm \mid k$.

$\bullet$ Conversely, if $nm \mid k, k = qnm, q\in \Z$, so $(ab)^k = a^k b^k = (a^m)^{qn} (b^n)^{qm} = e$.
$$\forall k \in \Z,\ (ab)^k = e \iff nm \mid k.$$
This proves $\vert ab \vert = nm$.
\end{proof}

\paragraph{Ex. 4.15}

{\it Let $K$ be a field and $G \subset K^*$ a finite subgroup of the multiplicative group of $K$.  Extend the arguments used in the proof of Theorem 4.1 to show that $G$ is cyclic.
}

\bigskip

 {\bf Solution 1.}

\begin{proof}
Let $n = \vert G \vert$. From Lagrange's theorem, $a^n = 1$ for all $a \in G$, so the polynomial $x^n-1\in K[x] $ has exactly $n$  distinct roots in $G$, and so
$$\forall x \in K,\ x \in G \iff x^n=1.$$

If $d \mid n$, the polynomial $x^d-1 \in K[x]$ has exactly $d$ roots in $K$ otherwise $x^n-1 = (x^d-1) g(x), g(x) \in K[x]$, and $\deg(g) = n-d$ has at most $n-d$ roots, so $x^n - 1$ would have less than $n$ roots in $K$. As $x_0^d = 1 \Rightarrow x_0^n = 1$, all these roots are in $G$ : $x^d - 1$ has $d$ roots in $G$.

Let $\psi(d)$ the number of elements in $G$ with order $d$ ($\psi(d) = 0$ if $d \nmid n$). Then $\sum_{c\mid d} \psi(c) = d$. Applying the M\"{o}bius inversion theorem, $\psi(d) = \sum_{c\mid d} \mu(c) d/c=\phi(d)$ (Prop. 2.2.5), in particular, $\psi(n) = \phi(n)\geq 1$. This proves the existence of an element of order $n$ in $G$, so $G$ is cyclic.

(Variation : $\psi(d) = 0$ if there exists no element of order $d$, and $\psi(d) = \phi(d)$ otherwise (see Ex.4.13). So $\psi(d) \leq \phi(d)$ for all $d\mid n$. As $\sum_{d\mid n} \psi(d) = \sum_{d\mid n} \phi(d) = n$, $\psi(d) = \phi(d)$ for all $d\mid n$. So there exists in $G$ an element of order $n$, and $G$ is cyclic.)
\end{proof}

\bigskip

{\bf Solution 2.}
\begin{proof}
Let $n = \vert G \vert = p_1^{a_1}\cdots p_k^{a_k}$. From Lagrange's theorem, $y^n = 1$ for all $y \in G$.

$p(x) = x^{n/p_1} - 1 \in K[x]$ has at most $n/p_1 < n$ roots in $K^*$, a fortiori in $G$, so there exists $a \in G$ such that $a^{n/p_1} \neq 1$.

Let $c_1 = a^{n/p_1^{a_1}} = a^{p_2^{a_2}\cdots p_k^{a_k}}$. Then $c_1^{p_1^{a_1}} = 1$ and $c_1^{p_1^{a_1-1}} = a^{n/p_1} \neq 1$, so $\vert c_1 \vert = p_1^{a_1} $.

Similarly, there exist $c_2,\ldots,c_k$ with respective orders $\vert c_i \vert = p_i^{a_i}$.

From exercise 4.14, we obtain by induction that $c =c_1\cdots c_k$ has order $ p_1^{a_1}\cdots p_k^{a_k} = n$, so $G$ is cyclic.
\end{proof}

\paragraph{Ex. 4.16}

{\it Calculate the solutions to $x^3 \equiv 1 \pmod {19}$ and $x^4 \equiv 1\pmod {17}$.
}

\begin{proof}
Here we note $a$ the class of $x$ in $\Z/p\Z$.

Let $a \in \F_{19}$. Then
$$a^3 - 1 = 0 \iff a-1 = 0 \text{ or }a^2+a+1=0.$$
\begin{align*}
a^2+a+1 = 0 &\iff (a + 10) - 99 = 0\\
&\iff (a+10)^2 - 4 = 0\\
&\iff (a+8)(a+12) = 0
\end{align*}
So, for all $x\in \Z$,
$$x^3 \equiv 1 \pmod {19} \iff x \equiv 1,7,11 \pmod {19}.$$

Let $a \in \F_{17}$.
\begin{align*}
a^4 = 1 &\iff a^2 = 1 \ \mathrm{or}\ a^2 = -1 = 4^2\\
&\iff a = \pm 1 \ \mathrm{or}\  a =\pm 4
\end{align*}
So, for all $x\in \Z$,
$$x^4 \equiv 1 \pmod {17} \iff x\equiv -1,1,-4,4 \pmod {17}.$$

Alternatively, we can take primitives roots modulo 19 and 17.

$2$ is a primitive root modulo $19$, Let $a = 2^k \in \F_{19}$.
\begin{align*}
a^3 = 1 &\iff 2^{3k} = 1\\
&\iff 18 \mid 3k\\
&\iff 6 \mid k\\
&\iff a = 1, 2^6 = 7, 2^{12} = 11
\end{align*}
$3$ is a primitive root modulo 17. Let $a = 3^k \in \F_{17}$.
\begin{align*}
a^4 = 1 &\iff 3^{4k} = 1\\
&\iff 16 \mid 4 k\\
&\iff 4 \mid k\\
&\iff a = 1, 3^4 = -4, 3^8 = -1, 3^{12} = 4
\end{align*}
\end{proof}

\paragraph{Ex. 4.17}

{\it 
Use the fact that $2$ is a primitive root modulo $29$ to find the seven solutions to $x^7 \equiv 1 \pmod {29}$.
}

\begin{proof}
Let $x \in \Z$, then $x \equiv 2^k \pmod{29} , k \in \N$.
\begin{align*}
x^7 \equiv 1 \pmod{29} &\iff 2^{7k} \equiv 1 \pmod {29}\\
&\iff 28 \mid 7k\\
&\iff 4 \mid k
\end{align*}
So the group cyclic  $S$ of the roots of $x^7 - 1$ in $\F_{29}$ are
$$S = \{1,2^4,2^8,2^{12},2^{16},2^{20},2^{24}\},$$
$$S = \{1,16,24,7,25,23,20\}.$$
\end{proof}

\paragraph{Ex. 4.18}

{\it Solve the congruence $1 + x + \cdots + x^6 \equiv 0 \pmod {29}$.
}

\begin{proof} As $(1 + x + \cdots + x^6)(1-x) = 1-x^7$,
$$1 + x + \cdots + x^6 \equiv 0 \pmod {29} \iff
\left\{
\begin{array}{ccc}
  x^7&  \equiv & 1 \pmod{29}  \\
  x &  \not \equiv &1 \pmod {29}      
\end{array}
\right.
$$
From Ex. 4.17, the solutions are congruent to $2^4,2^8,2^{12},2^{16},2^{20},2^{24}$ modulo $29$.
\end{proof}

\paragraph{Ex. 4.19}

{\it  Determine the numbers $a$ such that $x^3 \equiv a \pmod {p}$ is solvable for $p = 7, 11, 13$.
}

\begin{proof}
\begin{enumerate}
\item[(a)] If $p=7$, then $3 \mid p-1, d = 3\wedge (p-1) = 3$. From Prop. 4.2.1,
$$\exists x \in \Z, \ a \equiv x^3 \pmod 7 \iff a \equiv 0 \pmod 7 \ \mathrm{or}\ a^{(p-1)/3} = a^2 \equiv 1 \pmod  7.$$
So the numbers $a$ such that $x^3 \equiv a \pmod {7}$ is solvable are congruent at $0,1,-1$ modulo $7$.
\item[(b)]  If $p = 11$, then $d = 3 \wedge (p-1) = 1$. With the same proposition, 
$$\exists x \in \Z, \ a \equiv x^3 \pmod {11} \iff a \equiv 0 \pmod {11} \ \mathrm{or}\ a^{p-1} = a^6 \equiv 1 \pmod  {11}.$$
So all integers $a$ are cube modulo $11$, in only one way.

For an alternative proof, the application 
$$f : 
\left\{
\begin{array}{ccc}
  \F_{11}^*& \to   &\F_{11}^*  \\
  x & \mapsto   &   x^3
\end{array}
\right.
$$
$f$ is a bijection. Indeed,

$\bullet$ $f$ is a group homomorphism, 

$\bullet$ $x^3 = 1 \Rightarrow (x^3)^7 = 1 \Rightarrow (x^{10})^2 x = 1 \Rightarrow x=1$ thus $\ker(f) = \{1\}$, 

$\bullet$ $f:\F_{11}^*\to \F_{11}^*$ is injective and $\F_{11}^*$ is finite, hence $f$ is bijective.

In $\F_{11}$, $0=0^3,1=1^3,2=7^3,3=9^3,4=5^3,5=3^3,6=8^3,7=6^3,8=2^3,9=4^3,10 = 10^3$.
\item[(c)] If $p=13$, then $3 \mid p-1, 3 \wedge (p-1) = 3$, so
\begin{align*}
\exists x \in \Z, \ a \equiv x^3 \pmod {13} & \iff a \equiv 0 \pmod {13} \ \mathrm{or}\ a^{(p-1)/3} = a^4 \equiv 1 \pmod  {13}\\
&\iff a \equiv 0,1,-1,5,-5 \pmod {13}
\end{align*}
($5 \equiv 8^3 \pmod {13}$.)
\end{enumerate}
\end{proof}

\paragraph{Ex. 4.20}

{\it Let $p$ be a prime, and $d$ a divisor of $p - 1$. Show that $d$th powers form a subgroup of $U(\Z/p\Z)$ of order $(p-1)/d$. Calculate this subgroup for $p = 11, d = 5$, for $p = 17, d = 4$, and for $p = 19, d = 6$.
}

\begin{proof}
Here $p$ is a prime number, and $d \mid p-1$. Let
$$f : 
\left\{
\begin{array}{ccc}
  \F_p^*&  \to  &\F_p^*   \\
  x&  \to  &   x^d
\end{array}
\right.
$$
Then $f$ is a group homomorphism, and $\mathrm{im}(f)$ is the set of $d$th powers, and consequently is a subgroup of $U(\F_p) = \F_p^*$.
$\ker(f)$ is the group of the roots of $x^d-1$. As $d \mid p-1$, the polynomial $x^d-1$ has exactly $d$ roots (Prop. 4.1.2), so $\vert \ker(f) \vert = d$. 

As $\mathrm{im}(f) \simeq \F_p^* /\ker(f)$,
$$\vert \mathrm{im}(f) \vert = \vert \F_p^*  \vert / \vert \ker(f) \vert = (p-1)/d.$$
So there exist exactly $(p-1)/d$ $d$th powers in $(\Z/p\Z)^*$.

\bigskip

From Prop. 4.2.1, as $d \mid p-1, d \wedge (p-1)=d$, for all $x \in \F_p^*$, 

$$x \in \mathrm{im}(f) \iff x^{(p-1)/d} = 1.$$

So the group of $d$th powers is the group of the roots of $x^{(p-1)/d} - 1$.

$\bullet$ If $p=11,d=5$, $\mathrm{im}(f) = \{1,-1\}$.

$\bullet$ If $p = 17, d= 4$, $x \in \mathrm{im}(f) \iff x^4 = 1$ : $\mathrm{im}(f) = \{1,-1,4,-4\}$.

$\bullet$ If $p=19,d=6$, $x \in \mathrm{im}(f) \iff x^3 = 1$ : $\mathrm{im}(f) = \{1,7,7^2 = 11\}$, 

where $7 \equiv 2^6 \pmod {19}$.
\end{proof}

\paragraph{Ex. 4.21}

{\it If $g$ is a primitive root modulo $p$, and $d|p-1$, show that $g^{(p-1)/d}$ has order $d$. Show also that $a$ is a $d$th power iff $a \equiv g^{kd} \pmod p$ for some $k$. Do Exercises 16-20 making use of those observations.
}

\begin{proof}
Let $x = \overline{g}^{(p-1)/d} \in \F_p^*$, where $g$ is a primitive root modulo $p$. For all $k \in \Z$, 
\begin{align*}
x^k = 1 &\iff g^{k \frac{p-1}{d}} = 1\\
&\iff p-1 \mid k \frac{p-1}{d}\\
&\iff d \mid k
\end{align*}
So the order of $\overline{g}^{(p-1)/d}$ is $d$.

$\bullet$ If $\overline{a} = \overline{g}^{kd}$, then $\overline{a} = x^d$, where $x =\overline{g}^k$, so $\overline{a}$ is a $d$th power.

$\bullet$ If $\overline{a}\neq \overline{0}$ is a $d$th power, $\overline{a} = x^d, x \in \F_p^*$. As $x \in \langle \overline{g} \rangle$, $x = \overline{g}^k$, so $\overline{a} = \overline{g}^{kd}$.

So, if $a\not \equiv 0 \pmod p$, $a$ is a $d$th power iff $a \equiv g^{kd} \pmod p$ for some $k$.

By example (Ex. 4.20), $2$ is a primitive root modulo $19$, so the 6th powers modulo 19 are $2^0 = 1,2^6 = 7,2^{12} = 11$.
\end{proof}

\paragraph{Ex. 4.22}

{\it If $a$ has order $3$ modulo $p$, show that $1+a$ has order $6$.
}
\begin{proof}
If $a$ has order $3$ modulo $p$, then $0 \equiv a^3-1 = (a-1)(a^2+a+1) \pmod p$, with $a\not \equiv 1 \pmod p$, thus $a^2+a+1 \equiv 0 \pmod p$. Thus
\begin{align*}
(1+a)^3 &\equiv 1 + 3a +3a^2+a^3\\
&\equiv 1 + 3a +3(-1-a)+1\\
&\equiv -1 \pmod p
\end{align*}
So $(1+a)^6 \equiv 1 \pmod p$.

$(1+a)^2 \equiv 1+2a+a^2 =1+2a+(-1-a) \equiv a \not \equiv 1 \pmod p$. 

So $(1+a)^6 \equiv 1,  (1+a)^2 \not \equiv 1, (1+a)^3 \not \equiv 1 \pmod p$, therefore the order of $1+a$ divides $6$, but doesn't divides $2$ or $3$, thus $1+a$ has order $6$ modulo $p$.
\end{proof}

\paragraph{Ex. 4.23}

{\it Show that $x^2 \equiv -1 \pmod p$ has a solution iff $p \equiv 1 \pmod 4$, and that $x^4 \equiv -1 \pmod p$ has a solution iff $p \equiv 1 \pmod 8$.
}

\begin{proof}
If $x^2\equiv -1 \pmod p$, then  $\overline{x}$ has order 4 in  $\F_p^*$, hence from Lagrange's theorem, $4 \mid p-1$.

Conversely, suppose $4 \mid p-1$, so $p = 4k+1, k \in \N^*$.  From proposition 4.2.1, as $2 \mid p-1$, $-1$ is a square modulo $p$ iff $(-1)^{(p-1)/2} \equiv 1 \pmod p$, which is true because $(-1) ^{(p-1)/2} =(-1)^{2k} = 1$.

If $x^4 \equiv -1 \pmod p$, then $\overline{x}^8 = 1 \in \F_p^*$, and $\overline{x}^4 \ne 1$, so $\overline{x}$ has order $8$ in $\F_p^*$, so $8 \mid p-1$.

Conversely, if $p\equiv 1 \pmod 8$, $p = 8K+1, K\in \N^*$. From Prop.4.2.1, as $4 \mid p-1$, there exists $x \in \Z$ such that $-1 = x^4$ iff $(-1)^{(p-1)/4} \equiv 1 \pmod 8$, which is true because $(-1)^{(p-1)/4} = (-1)^{2K} = 1$.

Conclusion : 
$$\exists x \in \Z, \ x^4 \equiv -1 \pmod p \iff p \equiv 1 \pmod 8.$$
\end{proof}

\paragraph{Ex. 4.24}

{\it Show that $a x^m + b y^n \equiv c \pmod p$ has the same number of solutions as $a x^{m'} + b y^{n'} \equiv c \pmod p$, where $m' = (m,p-1)$ and $n' = (n, p-1)$.
}

\begin{proof}
If $a\wedge b \nmid c$, the two equations have no solution. So we can suppose $a\wedge b \mid c$, and after division by $\delta = a\wedge b$, we obtain an equation $a'x^m+b'y^n = c'$, $a' = a/\delta,b' = b\delta,c'=c\delta$, and $a' \wedge b' = 1$. So it remains to prove that $a x^m + b y^n \equiv c \pmod p$ has the same number of solutions as $a x^{m'} + b y^{n'} \equiv c \pmod p$ when $a\wedge b = 1$.

In this case the equation $au + bv=c$ has solutions. Let $N$ be the number of solutions $(\overline{x},\overline{y})$  of the equation $\overline{a}\, \overline{x}^m + \overline{b}\,  \overline{y}^n = \overline{c}$, and $N'$ be the number of solutions $(\overline{x},\overline{y})$  of the equation $\overline{a}\, \overline{x}^{m'} + \overline{b}\,  \overline{y}^{n' }= \overline{c}$. Then 
\begin{align*}
N &= \mathrm{Card} \{(\overline{x},\overline{y}) \in \F_p\times \F_p\ \vert\  \overline{a}\, \overline{x}^m + \overline{b}\,  \overline{y}^n = \overline{c}\}\\
&=\sum_{\overline{a}\overline{u}+\overline{b} \overline{v}=\overline{c}} \mathrm{Card} \{(\overline{x},\overline{y}) \in \F_p\times \F_p\ \vert\  \overline{x}^m = \overline{u} ,\overline{y}^n = \overline{v}\}\\
&= \sum_{\overline{a}\overline{u}+\overline{b} \overline{v}=\overline{c}} \mathrm{Card}\{\overline{x} \in \F_p\ \vert \overline{x}^m = \overline{u}\} \times \mathrm{Card}\{\overline{y} \in \F_p\ \vert \overline{y}^n = \overline{v}\}.
\end{align*}
The same is true for $N'$, so it is sufficient to prove that
$$\mathrm{Card}\{\overline{x} \in \F_p\ \vert\  \overline{x}^m  = \overline{u}\} = \mathrm{Card}\{\overline{x} \in \F_p\ \vert \ \overline{x}^{m'} = \overline{u}\},$$ 
where $m' = m \wedge (p-1)$, and a similar equality for the equation $\overline{y}^n = \overline{v}$.

Let $\overline{g}$ be a generator of $\F_p^*$. Write $\overline{u} = \overline{g}^r , r \in \N$.
\begin{align*}
\exists \overline{x} \in \F_p,\ \overline{x}^m = \overline{u} &\iff \exists k \in \Z, \ \overline{g}^{mk} = \overline{g}^r\\
&\iff \exists k \in \Z,\ p-1 \mid mk -r\\
&\iff \exists k \in \Z, \exists l \in \Z,\ r = mk + l (p-1)\\
&\iff m \wedge (p-1) \mid r
\end{align*}
Therefore $$\{\overline{x} \in \F_p\ \vert\  \overline{x}^m  = \overline{u}\} \ne \varnothing \iff m\wedge (p-1) \mid r,$$ and similarly $$\{\overline{x} \in \F_p\ \vert\  \overline{x}^{m'}  = \overline{u}\} \ne \varnothing \iff m' \wedge (p-1) \mid r.$$ 
Since $m' \wedge (p-1) = (m\wedge (p-1)) \wedge (p-1) = m \wedge (p-1)$, these two conditions are equivalent, so these two sets are empty for the same values of $\overline{u}$.

Let $\overline{u}$ be such that $\{\overline{x} \in \F_p\ \vert\  \overline{x}^m  = \overline{u}\} \ne \varnothing$, and $x_0$ be a fixed solution of $\overline{x}^m  = \overline{u}$.

Write $\overline{x} = \overline{g}^k, \overline{x_0} = g^{k_0}$. Let $d = m\wedge (p-1) (=m')$.
\begin{align*}
\overline{x}^m = u &\iff \overline{x}^m = \overline{x_0}^m\\
&\iff \overline{g}^{mk} = \overline{g}^{mk_0}\\
&\iff  p-1 \mid m(k -k_0)\\
&\iff \frac{p-1}{d} \mid \frac{m}{d} (k-k_0)\\
&\iff \frac{p-1}{d} \mid k-k_0\\
&\iff \exists j \in \Z,\ k = k_0 + j \frac{p-1}{d} 
\end{align*}
As $g$ is a primitive root modulo $p$, the distinct solutions are $x_0, x_0 g^{\frac{p-1}{d} },\ldots, x_0g^{k\frac{p-1}{d}}, \ldots x_0g^{ (d-1)\frac {p-1}{d}}$, therefore in this case
$$\mathrm{Card}\{\overline{x} \in \F_p\ \vert\  \overline{x}^m  = \overline{u}\} = d = m\wedge(p-1).$$
As $m'\wedge (p-1) = m\wedge (p-1)$,
$$\mathrm{Card}\{\overline{x} \in \F_p\ \vert\  \overline{x}^m  = \overline{u}\} = \mathrm{Card}\{\overline{x} \in \F_p\ \vert \ \overline{x}^{m'} = \overline{u}\}.$$ 
So $N=N'$ : $a x^m + b y^n \equiv c \pmod p$ has the same number of solutions as $a x^{m'} + b y^{n'} \equiv c \pmod p$, where $m' = (m,p-1)$ and $n' = (n, p-1)$.
\end{proof}

\paragraph{Ex. 4.25}

{\it Prove Propositions 4.2.2 and 4.2.4.
}

\medskip 

{\bf Proposition 4.2.2.} {\it Suppose that $a$ is odd, $e\geq 3$, and consider the congruence $x^n \equiv a \pmod {2^e}$. If $n$ is odd, a solution always exists and it is unique.

If $n$ is even, a solution exists iff $a \equiv 1 \pmod 4, a^{2^{e-2}/d} \equiv 1 \pmod{2^e}$, where $d = (n,2^{e-2})$. When a solution exists there are exactly $2d$ solutions.}
\begin{proof}
We suppose that $a$ is odd and $e \geq 3$.

 From Theorem 2', we know that $\{(-1)^a5^b\ \vert \ 0\leq a \leq 1, 0 \leq b \leq 2^{e-2}\}$ constitutes a reduced residue system modulo $2^e$, so we can write 
\begin{align*}
a &\equiv (-1)^s 5^t \pmod {2^e}, 0 \leq s \leq 1, 0 \leq t \leq 2^{e-2},\\
x &\equiv (-1)^y 5^z \pmod {2^e},0 \leq y \leq 1, 0 \leq z \leq 2^{e-2}.
\end{align*}
For all $x \in \Z$,
\begin{align*}
x^n \equiv a\pmod {2^e} &\iff (-1)^{ny} 5^{nz} \equiv (-1)^s 5^t \pmod {2^e}\\
\end{align*}
Then  $(-1)^{ny} \equiv (-1)^s \pmod4, ny\equiv s \pmod 2, (-1)^{ny} = (-1)^s$, thus $5^{nz} \equiv 5^t \pmod{2^e}$.

Conversely, if $ny \equiv s \pmod {2}$ and $5^{nz} \equiv 5^t \pmod{2^e}$, then $x^n\equiv a \pmod{2^e}$, so
$$
x^n\equiv a \pmod{2^e} \iff 
\left\{
\begin{array}{ccl}
  ny& \equiv   &s \pmod{2}   \\
  5^{nz}& \equiv  &    5^t \pmod {2^{e}}
\end{array}
\right.
\iff 
\left\{
\begin{array}{ccl}
  ny& \equiv   &s \pmod{2}   \\
  nz& \equiv  &    t\pmod {2^{e-2}}
\end{array}
\right.
$$
since the order of 5 modulo $2^e$ is $2^{e-2}$.

$\bullet$ Suppose that $n$ is an odd integer. Then
$$
\left\{
\begin{array}{ccl}
  ny& \equiv   &s \pmod{2}   \\
  nz& \equiv  &    t\pmod {2^{e-2}}
\end{array}
\right.
\iff
\left\{
\begin{array}{ccl}
  y& \equiv   &s \pmod{2}   \\
  z& \equiv  &   n' t\pmod {2^{e-2}}
\end{array}
\right.
$$
where $n'$ is an inverse of $n$ modulo $2^{e-2}$ : $nn'\equiv 1 \pmod {2^{e-2}}$.

So $x^n\equiv a \pmod{2^e}$ has an unique solution modulo $2^e$.

$\bullet$ Suppose that $n$ is an even integer. 

Then $\left\{
\begin{array}{ccl}
  ny& \equiv   &s \pmod{2}   \\
  nz& \equiv  &    t\pmod {2^{e-2}}
\end{array}
\right.
$ implies $s \equiv 0 \pmod 2$ and $d = n\wedge2^{e-2} \mid t$.

Then $a \equiv (-1)^s 5^t \equiv 5^t  \pmod {2^{e}}$, so $a\equiv 1 \pmod 4$.

 Hence $a^{\frac{2^{e-2}}{d}} \equiv \left(5^{2^{e-2}}\right)^{\frac{t}{d}}\equiv 1 \pmod {2^e}$, since $5$ has order $2^{e-2}$, and $d\mid t$. 
 
 So, if $n$ is even, and, with $d =  n\wedge2^{e-2}$, 
 $$\exists x \in \Z,\ x^n\equiv a \pmod{2^e} \Rightarrow 
 \left\{
 \begin{array}{ccl}
  a& \equiv   &1 \pmod{4},   \\
  a^{\frac{2^{e-2}}{d}} & \equiv  &    1 \pmod {2^{e}}.
\end{array}
\right.
$$
Conversely, suppose that $\left\{
 \begin{array}{ccl}
  a& \equiv   &1 \pmod{4},   \\
  a^{\frac{2^{e-2}}{d}} & \equiv  &    1 \pmod {2^{e}}.
\end{array}
\right.$

Then $a\equiv(-1)^s 5^t \pmod {2^e} $ implies $ a \equiv (-1)^s \pmod 4$, so $s$ is even, and $a \equiv 5^t \pmod{2^e}$.

Therefore $5^{t \frac{2^{e-2}}{d}} \equiv 1 \pmod {2^e}$, which  implies $2^{e-2} \mid t \frac{2^{e-2}}{d}$, so $d \mid t$.
\begin{align*}
\exists x \in \Z,\ x^n\equiv a \pmod{2^e} &\iff \exists y \in \Z,\ \exists z \in \Z,\ \left\{
\begin{array}{ccl}
  ny& \equiv   &s \pmod{2}   \\
  nz& \equiv  &    t\pmod {2^{e-2}}
\end{array}
\right.\\
&\iff \exists z \in \Z,\ nz \equiv t \pmod{2^{e-2}}\qquad (\mathrm{since}\ n,s\ \mathrm{even})\\
&\iff \exists z \in \Z,\ 2^{e-2} \mid nz - t\\
&\iff \exists z \in \Z,\ \frac{2^{e-2}}{d} \mid \frac{n}{d} z - \frac{t}{d}\\
&\iff \exists z \in \Z,\ \exists q \in \Z, \ q \frac{2^{e-2}}{d} + z \frac{n}{d}   = \frac{t}{d}
\end{align*}
As $\frac{2^{e-2}}{d} \wedge \frac{n}{d} = 1$, there exists a solution $(q,z_0)$ of this last equation, where $0\leq z_0 < \frac{2^{e-2}}{d}$, and so $x_0 = 5^{z_0}$ is a particular solution of $x^n\equiv a \pmod{2^e}$, therefore
 $$\exists x \in \Z,\ x^n\equiv a \pmod{2^e} \iff
 \left\{
 \begin{array}{ccl}
  a& \equiv   &1 \pmod{4}   \\
  a^{\frac{2^{e-2}}{d}} & \equiv  &    1 \pmod {2^{e}}
\end{array}
\right.
$$
If there exists a particular solution $x_0 \equiv (-1)^{y_0}5^{z_0}$, then
\begin{align*}
x^n \equiv a \pmod{2^e} &\iff x^n\equiv x_0^n \pmod {2^e}\\
&\iff
\left\{
\begin{array}{ccl}
  ny& \equiv   &ny_0 \pmod{2}   \\
  nz& \equiv  & nz_0   \pmod {2^{e-2}}
\end{array}
\right.\\
&\iff n(z -z_0)\equiv   0   \pmod {2^{e-2}} \qquad(\mathrm{since}\ n\  \mathrm{even})\\
&\iff \frac{2^{e-2}}{d} \mid \frac{n}{d} (z-z_0)\\
&\iff \frac{2^{e-2}}{d} \mid z-z_0,\qquad (\mathrm{since} \ \frac{2^{e-2}}{d} \wedge \frac{n}{d} = 1)\\
&\iff \exists k \in \Z, \ z = z_0+ k \frac{2^{e-2}}{d}
\end{align*}
As the order of $5$ modulo $2^e$ is $2^{e-2}$, the solutions of $x^n \equiv a \pmod{2^e}$ are $$x_k = (-1)^y 5^{z_0+ k \frac{2^{e-2}}{d}},\  0\leq y < 2,\  0\leq k < d,$$ so there are exactly $2d$ solutions modulo $2^e$.
\end{proof}

\bigskip
{\bf Proposition 4.2.4.} 
{\it Let $2^l$ be the highest power of $2$ dividing $n$. Suppose that $a$ is odd and that $x^n \equiv a \pmod {2^{2l+1}}$ is solvable. Then $x^n \equiv a \pmod{2^e}$ is solvable for all $e\geq 2l+1$ (and consequently for all $e\geq 1$). Moreover, all these congruences have the same number of solutions.
}
\begin{proof}
We suppose that $a$ is odd, and that $x^n\equiv a \pmod {2^{2l+1}}$ is solvable. $l$ is such that $n = 2^l n'$, where $n'$ is an odd integer.

Let the induction hypothesis  be, for a fixed integer $m\geq 2l+1$,
$$\exists x_0 \in \Z,\  x_0^n\equiv a \pmod{2^m}.$$
Let $x_1 = x_0 + b 2^{m-l}$. We show that for an appropriate choice of $b\in \{0,1\}$,  $x_1^n \equiv a \pmod {2^{m+1}}$.

$x_1^n = x_0^n + nb2^{m-l}x_0^{n-1} + 2^{2m-2l} A,\  A \in \Z$.

Since $m\geq 2l+1, 2m-2l \geq m+1$, so
$$x_1^n \equiv x_0^n + nb2^{m-l}x_0^{n-1} \pmod {2^{m+1}}.$$
\begin{align*}
x_1^n \equiv a \pmod {2^{m+1}} &\iff (x_0^n -a) + n' b x_0^{n-1} 2^m \equiv 0 \pmod {2^{m+1}}\\
&\iff\frac{x_0^n - a}{2^m} + n' b x_0^{n-1} \equiv 0 \pmod 2
\end{align*}
As $a$ is odd, and  $x_0^n \equiv a \pmod {2^m}, m\geq 1$, $x_0$ is odd, and $n'$ is odd, so there exists an unique $b \in \{0,1\}$ such that $\frac{x_0^n - a}{2^m} + n' b x_0^{n-1} \equiv 0 \pmod 2$. Hence there exists $x_1 \in \Z$ such that $x_1^n \equiv a \pmod {2^{m+1}}$, and the induction is done. Therefore, $x^n \equiv a \pmod{2^e}$ is solvable for all $e\geq 2l+1$, and consequently for all $e\geq 1$. 

\bigskip

From the Proposition 4.2.2., with the hypothesis $e\geq 3$,  we know that the number of solutions of the solvable equation $x^n \equiv a \pmod {2^e}, e\geq 2l+1$,  is $1$ if $n$ is odd, $2(n\wedge 2^{e-2})$ if $n$ is even.

If $n$ is even, $l\geq 1$, $e \geq 2l+1 \geq 3$.
Since $e\geq 2l+1$, and $n = 2^l n'$ for an odd $n'$, $l\leq \frac{e-1}{2} \leq e-2$, so $n \wedge 2^{e-2} = n'2^{l} \wedge 2^{e-2}= 2^l$, and the number of solutions is $2^{l+1}$, independent of $e\geq 2l+1$.

Conclusion: Under the hypothesis $x^n \equiv a \pmod {2^{2l+1}}$, where $l = \mathrm{ord}_2(n)$, then $x^n \equiv a \pmod {2^e}$ is solvable for all $e\geq 1$, and all these congruences have the same number of solutions for $e\geq 2l+1, e\geq 3$.
\end{proof}

\newpage


{ \Large \bf Chapter 5}

\paragraph{Ex. 5.1}

{\it  Use Gauss' lemma to determine $\legendre{5}{7}, \legendre{3}{11}, \legendre{6}{13},\legendre{-1}{p}$.
}

\begin{proof}
$\bullet$ $a = 5, p=7$.

The array of values of the least residues modulo $p=7$, for $1\leq k \leq (p-1)/2$.
$$
\begin{array}{rcccc}
  k & \vline & 1 & 2 & 3\\
 \hline
    5k \mod 7& \vline & -2  & 3 & 1
\end{array}
$$
So  the number of negative least residues is $\mu = 1$, and $\legendre{5}{7} =(-1)^{\mu} =  -1$.

$\bullet$ $a=3,p=11$.
$$
\begin{array}{rcccccc}
  k & \vline & 1 & 2 & 3 &4 &5 \\
 \hline
    3k \mod 11& \vline & 3  & -5 & -2 & 1&  4
\end{array}
$$
So $\mu = 2$, $\legendre{3}{11} = (-1)^\mu = 1$.

$\bullet$ $a=6,p=13$.
$$
\begin{array}{rccccccc}
  k & \vline & 1 & 2 & 3 &4 &5 &6\\
 \hline
    6k \mod 13& \vline & 6  & -1& 5 & -2 &  4& -3
\end{array}
$$
So $\mu = 3$, $\legendre{6}{13} = (-1)^\mu = -1$.

$\bullet$ If $a=-1$, and $p$ is an odd prime, the values of the least residues of $-k$ modulo $p$ for $k=1,2,\ldots,(p-1)/2$ are $-k$, all negative. So  the number of negative least residues is $\mu = (p-1)/2$, and 
$\legendre{-1}{p} = (-1)^{(p-1)/2}$.
\end{proof}

\paragraph{Ex. 5.2}

{\it  Show that the number of solutions to $x^2 \equiv a \pmod p$ is equal to $1 + (a/p)$.
}

\begin{proof} Let $N$ be the number of solutions of $x^2\equiv a \pmod p$.

$\bullet$ If $\legendre{a}{p} = 0$, then $p\mid a$, $a\equiv 0 \pmod p$, so the unique solution of $x^2 \equiv a = 0$ is $x\equiv 0 \pmod p$, so $N = 1 = 1 + \legendre{a}{p}$.

$\bullet$ If $\legendre{a}{p} = -1$, then $N = 0 = 1 + \legendre{a}{p}$.

$\bullet$ If $\legendre{a}{p} = 1$, then $x^2\equiv a \pmod p$ has a solution $x_0$, and $x^2 \equiv a \pmod p\iff x^2 \equiv x_0^2 \pmod p\equiv p \mid (x-x_0)(x+x_0) \equiv x\equiv \pm x_0 \pmod p$, so $N = 2 = 1 + \legendre{a}{p}$.
\end{proof}

\paragraph{Ex. 5.3}

{\it Suppose $p \not | \; a$. Show that the number of solutions to $a x^2 + bx + c \equiv 0 \pmod p$ is equal to $1 + ((b^2- 4ac)/p)$.
}

\begin{proof}
Here $p$ is an odd prime number, and $p \nmid a$. Let $N$ be the number of solutions of $a x^2 + bx + c \equiv 0 \pmod p$

For $\overline{x} \in \F_p = \Z/p\Z$, 
\begin{align*}
\overline{a} \overline{x}^2 + \overline{b}\overline{x} + \overline{c} &= \overline{a}\left( \overline{x}^2 + \frac{\overline{b}}{\overline{a}}\ \overline{x} + \frac{\overline{c}}{\overline{a}}\right)\\
&=\overline{a} \left( \left(\overline{x} + \frac{\overline{b}}{2\overline{a}}\right)^2 - \frac{\overline{b}^2 - 4 \overline{a}\overline{c}}{4 \overline{a}^2} \right)
\end{align*}
Let $\Delta = b^2-4ac$. Then $N$ is the number of solutions of $\left(\overline{x} + \frac{\overline{b}}{2\overline{a}}\right)^2 - \frac{\overline{\Delta}}{4 \overline{a}^2} = \overline{0}$ in $\F_p$. As in Ex.5.2,  $N = 1$ if $\overline{\Delta} = \overline{0}$, $N=0$ if $\overline{\Delta}$ is not a square in $\F_p^*$,  otherwise $\overline{\Delta} = \delta^2, \delta \in \F_p^*$, and the solutions are $\overline{x} = (-\overline{b} \pm \overline{\delta})/ 2\overline{a}$, so  $N = 2$. In the three cases, $N = 1+ \legendre{\Delta}{p}$. 
\end{proof}

\paragraph{Ex. 5.4}

{\it Prove that $\sum_{a=1}^{p-1} (a/p) = 0$.
}

\begin{proof} Here $p$ is an odd  prime (the result is false if $p=2$). In the interval $[1,p-1]$, there exist $(p-1)/2$ residues, and $(p-1)/2$ nonresidues (Prop. 5.1.2., Corollary 1), so $\sum_{a=1}^{p-1} (a/p) = 0$.
\end{proof}

\begin{proof}
As an alternative proof, let $S = \sum\limits_{a=1}^{p-1} \legendre{a}{p}$, and  $b$ a nonresidue modulo $p$ : $\legendre{b}{p} = -1$ (such a $b$ exists if $p\neq 2$). As $a \mapsto ab$ is a bijection from $\F_p^*$ to itself, 
$$\legendre{b}{p} S = \sum_{a=1}^{p-1} \legendre{ab}{p} = \sum_{c = 1}^{p-1} \legendre{c}{p}  = S,$$
so $-S = S, S=0$.
\end{proof}

\paragraph{Ex. 5.5}

{\it  Prove that $\sum_{x=1}^{p-1} ((ax + b)/p) = 0$ provided that $p \nmid a$.}

There is a mistake in the sentence : we must read 

{\it  Prove that $\sum_{x=0}^{p-1} ((ax + b)/p) = 0$ provided that $p \nmid a$.}

For instance, 
$$\sum_{x=1}^{5-1} \legendre{x+1}{5} = \legendre{2}{5} +  \legendre{3}{5}+  \legendre{4}{5} = -1\neq 0.$$
\begin{proof} 
From exercise 5.3, as $\legendre{0}{p} = 0$, we know that
$$\sum_{\overline{x} \in \F_p} \legendre{x}{p} = \sum _{x=0}^{p-1} \legendre{x}{p} = \sum_{x=1}^{p-1} \legendre{x}{p} =0.$$

(This sum is well defined, since $\legendre{x}{p}$ depends only of $\overline{x}$ : $x\equiv x' \pmod p \Rightarrow \legendre{x}{p} =\legendre{x'}{p}$.)

As $\overline{a} \neq \overline{0}$ in $\F_p$,
$
f :
\left\{
\begin{array}{ccc}
  \F_p &\to   &\F_p   \\
  x & \mapsto   & \overline{a} x+\overline{b}
 \end{array}
\right.
$ is a bijection. Thus
\begin{align*}
\sum_{x=0}^{p-1} \legendre{ax+b}{p} & = \sum_{x \in \F_p} \legendre{f(x)}{p}\\
&=\sum_{y \in \F_p} \legendre{y}{p}\qquad (y = f(x))\\
&= 0
\end{align*}
\end{proof}

\paragraph{Ex. 5.6}

{\it  Show that the number of solutions to $x^2 - y^2 \equiv a \pmod p$ is given by:
$$
  \sum_{y=0}^{p-1}\left(1+\legendre{y^2 + a}{p}\right).
$$

}

\begin{proof}
Let $S =\{(\overline{x},\overline{y}) \in \F_p^2\ \vert \ \overline{x}^2 - \overline{y}^2 = \overline{a}\} $.
From Ex.5.2,
\begin{align*}
\vert S \vert &= \sum_{\overline{y} \in \F_p} \mathrm{Card} \ \{\overline{x} \in \F_p\ \vert \ \overline{x}^2 = \overline{y}^2 + \overline{a}\} \\
&= \sum_{y=0}^{p-1}\left(1+\legendre{y^2 + a}{p}\right).
\end{align*}
\end{proof}

\paragraph{Ex. 5.7}

{\it 
By calculating directly show that the number of solutions to $x^2 - y^2 \equiv a \pmod p$ is $p-1$ if $p \nmid a$, and $2p - 1$ if $p \mid a$. (Hint. Use the change of variables $u = x+y, v=x-y$.)

}

\begin{proof}
Let $S = \{(\overline{x},\overline{y}) \in \F_p^2\ \vert \ \overline{x}^2 - \overline{y}^2 = \overline{a}\}$, and $T = \{(\overline{u},\overline{v}) \in \F_p^2\ \vert \ \overline{u}\, \overline{v} = \overline{a}\}$.
Then 
$f:
\left\{
\begin{array}{ccc}
 S &  \to  &  T\\
  (\overline{x},\overline{y})&  \mapsto &  (\overline{x} + \overline{y},  \overline{x} - \overline{y})
\end{array}
\right.
$ is well defined (if $(\overline{x},\overline{y}) \in S, (\overline{x}-\overline{y})(\overline{x}+\overline{y}) =a$, so $(\overline{x} + \overline{y},  \overline{x} - \overline{y}) \in T$). Moreover $f$ is a bijection, with inverse $(\overline{u},\overline{v}) \mapsto  ((\overline{u}+ \overline{v})/2, (\overline{u}- \overline{v})/2)$, so $\vert S \vert = \vert T \vert$.

We compute $\vert T \vert$.

$\bullet$  Suppose that $p\nmid a$, so $\overline{a} \neq \overline{0}$. For $\overline{v} = {0}$, there is no solution, and for each $\overline{v} \neq 0$, we obtain the unique solution $(\overline{a} \, \overline{v}^{-1},\overline{v})$, so there exist $p-1$ solutions.

$\bullet$ Suppose that $p\mid a$. The solutions of $\overline{u} \overline{v} = \overline{0}$ are $(\overline{0},\overline{0})$ if $\overline{u} = \overline{v} = \overline{0}$, $(\overline{0},\overline{v})$ for each $\overline{v} \ne \overline{0}$, and $(\overline{u},\overline{0})$ for each $\overline{v} =\overline{0}$, that is to say $N = 1+(p-1)+(p-1) = 2p-1$ solutions.

Conclusion : 
\begin{align*}
\mathrm{Card} \ \{(\overline{x},\overline{y}) \in \F_p^2\ \vert \ \overline{x}^2 - \overline{y}^2 = \overline{a}\} &= p-1\quad \mathrm{if}\  p \nmid a\\
&= 2p-1 \quad \mathrm{if}\  p \mid a\\
\end{align*}
\end{proof}

\paragraph{Ex. 5.8}

{\it Combining the results of Ex. 5.6 and 5.7 show that:
$$
  \sum_{y=0}^{p-1} \left(\frac{y^2 +a}{p}\right) =
  \begin{cases}
   \  -1 \ \quad \mathrm {if}\ p\nmid a \\
   \  p-1 \quad \mathrm{if}\, p \mid a
  \end{cases}
$$
}

\begin{proof}
Let $S =\{(\overline{x},\overline{y}) \in \F_p^2\ \vert \ \overline{x}^2 - \overline{y}^2 = \overline{a}\} $.

We obtain in Ex 5.6, $\vert S \vert =    \sum\limits_{y=0}^{p-1}\left(1+\legendre{y^2 + a}{p}\right)$, and in Ex. 5.7. , $\vert S \vert  =  p-1$ if $p\nmid a$, $\vert S \vert  =  2p-1$ if $p\mid a$.

Therefore $$|S| - p = \sum\limits_{y=0}^{p-1} \legendre{y^2 + a}{p} = 
 \begin{cases}
   \  -1 \ \quad \mathrm {if}\ p\nmid a \\
   \  p-1 \quad \mathrm{if}\, p \mid a
  \end{cases}
  $$
\end{proof}

\paragraph{Ex. 5.9}

{\it  Prove that $1^2 3^2 \cdots (p-2)^2 \equiv (-1)^{(p+1)/2} \pmod p$ using Wilson's theorem.
}

\begin{proof}
Here $p$ is an odd prime.

From Wilson's theorem, as $k(p-k) \equiv -k^2 \pmod p$ for $k=1,2,\ldots,p-1$,
\begin{align*}
-1&\equiv (p-1)!\\
&\equiv \left[1\times 2\times\cdots\times k\times \cdots\times\left(\frac{p-1}{2}\right)\right]\times\left[\left(\frac{p+1}{2}\right)\times\cdots\times(p-k)\cdots\times(p-2)\times(p-1)\right]\\
&\equiv \prod_{k=1}^{(p-1)/2} k(p-k)\\
&\equiv (-1)^{(p-1)/2} \prod_{k=1}^{(p-1)/2} k^2 \\
&\equiv (-1)^{(p-1)/2}\left[\left(\frac{p-1}{2}\right)!\right]^2 \pmod p
\end{align*}
Therefore $$\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p+1)/2} \pmod p.$$
Moreover, from Wilson' theorem and Fermat's little theorem,
\begin{align*}
1^2 2^23^2\cdots(p-1)^2 &= [(p-1)!]^2 \equiv 1 \pmod p,\\
2^2 4^2 \cdots(p-1)^2 &=\left(2^{p-1}\right)^2 \left[\left(\frac{p-1}{2}\right)!\right]^2\equiv \left[\left(\frac{p-1}{2}\right)!\right]^2 \pmod p.\\
\end{align*}
Thus
$$1^2 3^2\cdots(p-2)^2 \left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv 1 \pmod p,$$
which gives
$$1^2 3^2\cdots(p-2)^2 \equiv (-1)^{(p+1)/2} \pmod p.$$
\end{proof}

\paragraph{Ex. 5.10}

{\it Let $r_1, r_2, \ldots, r_{(p-1)/2}$ be the quadratic residues between
$1$ and $p$. Show that their product is congruent to $1 \pmod p$ if $p
\equiv 3 \pmod 4$, and to $-1$ if $p \equiv 1 \pmod 4$.

}

\begin{proof}
We have proved in Ex. 5.9 that
$$\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p+1)/2} \pmod p.$$
The application 
$ f:
\left\{
\begin{array}{ccc}
\{\overline{1},\overline{2},\ldots,\overline{(p-1)/2}\}  & \mapsto    & \{ \overline{r_1},\overline{ r_2}, \ldots, \overline{r_{(p-1)/2}}\} \\
  x &  \mapsto  &  x^2   
\end{array}
\right.
$ is a bijection, so
$$\prod_{i=1}^{(p-1)/2} r_i \equiv \left[\left(\frac{p-1}{2}\right)!\right]^2 \pmod p,$$
so
$$\prod_{i=1}^{(p-1)/2} r_i \equiv (-1)^{(p+1)/2} \pmod p.$$
That is to say, the product of the quadratic residues between $1$ and $p$ is congruent to $1 \pmod p$ if $p
\equiv 3 \pmod 4$, and to $-1$ if $p \equiv 1 \pmod 4$.
\end{proof}

\paragraph{Ex. 5.11}

{\it  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$.
}

\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 \times 89$.
\end{proof}

\paragraph{Ex. 5.12}

{\it Let $f(x) \in \Z[x]$. We say that a prime $p$ divides $f(x)$ if there's an integer $n$ such that $p \mid f(n)$. Describe the prime divisors of $x^2 + 1$ and $x^2 -2$.
}

\begin{proof}
$p$ divides $x^2+1$ iff there exists $a \in \Z$ such that $-1 \equiv a^2 \pmod p$, iff $p=2$ or $\legendre{-1}{p} = 1$ iff $ p=2$ or $p \equiv 1 \pmod 4$.

$p$ divides $x^2-2$ iff there exists $a \in \Z$ such that $2 \equiv a^2 \pmod p$, iff $p=2$ or  $\legendre{2}{p} = 1$ iff $p=2$ or $p \equiv \pm 1 \pmod 8$.
\end{proof}

\paragraph{Ex. 5.13}

{\it  Show that any prime divisor of $x^4 - x^2 + 1$ is congruent to $1$ modulo $12$.
}

\begin{proof}

$\bullet$ As $a^6 +1 = (a^2+1)(a^4-a^2+1)$, $p\mid a^4 - a^2+1$ implies $p \mid a^6 + 1$, thus $\legendre{-1}{p} = 1$ and $p\equiv 1 \pmod 4$.

$\bullet$ $p \mid 4a^4 - 4 a^2 +4 = (2a-1)^2 + 3$, so $\legendre{-3}{p} = 1$.

As $-3 \equiv 1 \pmod 4$, $\legendre{-3}{p} = \legendre{p}{3}$, therefore $\legendre{p}{3} = 1$, thus $p \equiv 1 \pmod 3$.

$4 \mid p-1$ and $3 \mid p-1$, with $3 \wedge 4 = 1$,  thus $12 \mid p-1$ : $$p \equiv 1 \pmod {12}.$$
\end{proof}

\paragraph{Ex. 5.14}

{\it Use the fact that $U(\Z/p\Z)$ is cyclic to give a direct proof that $(-3/p) = 1$ when $p \equiv 1 \pmod 3$.[Hint : There is a $\rho$ in $U(\Z/p\Z)$ of order $3$. Show that $(2\rho + 1)^2 = -3$.]
}

\begin{proof}
Suppose that $p\equiv 1 \pmod 3$. Let $g$ a generator of $\F_p^*$. Then $g$ has order $p-1$, thus $\rho = g^{(p-1)/3}$ has order $3$.
As $\rho^3 = 1,\rho\ne 1$, then $\rho^2+\rho+1 = 0$.
\begin{align*}
(2\rho + 1)^2 &= 4\rho^2+ 4\rho +1\\
&=4(\rho^2+\rho+1)-3\\
&=-3.
\end{align*}
Thus $\legendre{-3}{p} = 1$.
\end{proof}
The converse is also true for an odd prime $p$ :  if $\legendre{-3}{p} = 1$, then there exists $a\in \F_p^*$ such that $-\overline{3} =a^2$. Then $\rho = \frac{-1+a}{2} (=(-1+a)2^{-1})$ has order  $3$. Indeed
$\rho^2 = \frac{1+a^2-2a}{4} = \frac{-2-2a}{4} = \frac{-1-a}{2}$, so
\begin{align*}
1+\rho + \rho^2 &= 1 +  \frac{-1+a}{2}+ \frac{-1-a}{2}\\
&=0
\end{align*}
thus $\rho\ne1, \rho^3=1$.
The group $\F_p^*$ contains an element of order 3, therefore, by Lagrange's theorem, $3 \mid p-1$, that is $p\equiv 1 \pmod 3$.

\paragraph{Ex. 5.15}

{\it If $p \equiv 1 \pmod 5$, show directly that $(5/p) = 1$ by the method of Ex. 5.14. [Hint : Let $\rho$ be an element of $U(\Z/p\Z))$ of order $5$. Show that $(\rho+\rho^4)^2+ (\rho+\rho^4)-\overline{1}= \overline{0}$, etc.]
}

\begin{proof}
Let $g$ be a generator of $\F_p^*$. Then $g$ has order $p-1$, thus $\rho = g^{(p-1)/5}$ has order $5$.

Let 
$$
\left\{
\begin{array}{ccc}
  \alpha & =  & \rho + \rho^4  \\
  \beta &   = &  \rho^2 + \rho^3   
\end{array}
\right.
$$
As $0 = \rho^5- 1 = (\rho - 1)(1+\rho+\rho^2+\rho^3+\rho^4)$ and $\rho \neq 1$, then $1+\rho+\rho^2+\rho^3+\rho^4=0$, thus
\begin{align*}
\alpha+ \beta &= -1\\
\alpha\beta &= \rho^3+\rho^4+ \rho +\rho^2 = -1
\end{align*}
This shows that $\alpha,\beta$ are the roots in $\F_p$ of $x^2 +x - 1$, so that $\alpha^2+\alpha-1 = 0$.

Thus $4\alpha^2+4\alpha - 4 = (2\alpha+1)^2 - 5 = 0$ : $\overline{5}$ is a square in $\F_p^*$ and $\legendre{5}{p} = 1$.
\end{proof}

\paragraph{Ex. 5.16}

{\it  Using quadratic reciprocity find the primes for which $7$ is quadratic residue. Do the same for $15$.
}

\begin{proof}
$7$ is a quadratic residue for $2$ and for the odd primes such that $\legendre{7}{p} = 1$.

From the law of quadratic reciprocity,
\begin{align*}
\legendre{7}{p} = 1 \iff (-1)^{(p-1)/2} \legendre{p}{7} = 1
\end{align*}
iff either $p\equiv 1 \pmod 4$ and $\legendre{p}{7} =1$, or $p\equiv -1 \pmod 4$ and $\legendre{p}{7} =-1$.

In the first case , $p\equiv 1 \pmod 4, p\equiv 1,4,2 \pmod 7$, which gives $p \equiv 1,-3,9 \pmod {28}$.

In the second case, $p\equiv -1 \pmod 4, p\equiv -1,-4,-2 \pmod 7$, which gives $p\equiv -1,3,-9 \pmod {28}$.

Conclusion : the primes for which $7$ is a  quadratic residue are $2$ and the odd primes $p$ such that
$$\legendre {7}{p} = 1 \iff p \equiv \pm 1,\pm 3, \pm 9 \pmod{28}.$$
\end{proof}

\bigskip

$15$ is a  quadratic residue for $2$ and for the odd primes such that $\legendre{15}{p} = 1$.
\begin{align*}
\legendre{15}{p} = 1 \iff \legendre{3}{p} = \legendre{5}{p} = 1\ \mathrm{or} \ \legendre{3}{p} = \legendre{5}{p} = -1
\end{align*}
From the examples of theorem 2, we know that
$$\legendre{3}{p} = 1 \iff p\equiv 1,-1 \pmod {12}, \quad \legendre{3}{p} = -1 \iff  p \equiv  5 ,-5\pmod {12},$$
$$\legendre{5}{p} = 1 \iff p \equiv 1,-1 \pmod {5}, \quad \legendre{5}{p} = -1 \iff p \equiv 2,-2 \pmod {5}.$$
As $5\wedge 12 = 1$, there exist 8 cases, all possible, which give
$$\legendre{15}{p} = 1 \iff p \equiv \pm 1,\pm 7, \pm 11, \pm 17 \pmod {60}.$$
For instance, the primes $2,7,11,17, 43, 53,59,  61,67, 137, \ldots$ are suitable.

\paragraph{Ex. 5.17}

{\it Supply the details to the proof of Proposition 5.2.1 and to the corollary to the lemma following it.
}

\medskip

{\bf Proposition 5.2.1} 
{\it
\begin{enumerate}
\item[(a)] $(a_1/b) = (a_2/b)$ if $a_1\equiv a_2 \pmod b$.
\item[(b)] $(a_1a_2/b) = (a_1/b)(a_2/b)$.
\item[(c)] $(a/b_1b_2) = (a/b_1)(a/b_2)$.
\end{enumerate}
}
\begin{proof}  
\begin{enumerate}
\item[(a)] Let $b = p_1p_2\cdots p_m$, where the $p_i$ are not necessarily distinct primes.
For each prime $p_i$, $(a_1,p_i) = (a_2,p_i)$ (Prop. 5.1.2 (c)), so $\prod_i (a_1,p_i) = \prod_i (a_2,p_i)$, thus $(a_1/b) = (a_2/b)$.
\item[(b)] From Prop. 5.1.2(b), 

$(a_1a_2/b) = \prod_i (a_1a_2/p_i) = \prod_i (a_1/p_i)(a_2/p_i) =\prod_i (a_1/p_i)\prod_i (a_2/p_i) = (a_1/b)(a_2/b)$.

\item[(c)] Let $b_1 = p_1p_2\cdots p_m, b_2 = q_1 q_2\cdots q_l$. Then $b_1b_2 = p_1p_2\cdots p_m q_1 q_2\cdots q_l = \prod_{i=1}^{m+l} r_i$, where $r_i = p_i$ for $i=1,\ldots,m$, $r_i = q_{i-m}$ for $i = m+1,\ldots, m+l$. Then

$(a/b_1b_2) =\prod_{i=1}^{m+l} (a/ r_i) =  \prod_{i=1}^m (a/p_i) \prod_{j=1}^l(a/q_i) = (a/b_1)(a/b_2)$. 
\end{enumerate}
\end{proof}


{\bf Lemma.} {\it Let $r$ and $s$ be odd integers. Then
\begin{enumerate}
\item[(a)] $(rs-1)/2 \equiv ((r-1)/2) + ((s-1)/2) \pmod 2$.
\item[(b)] $(r^2s^2 - 1)/8 \equiv ((r^2-1)/8) + ((s^2-1)/8)\pmod 2$.
\end{enumerate}
\it}

(Proof in the book.)

\bigskip

{\bf Corollary.} {\it Let $r_1,r_2,\ldots,r_m$ be odd integers. Then
\begin{enumerate}
\item[(a)] $\sum_{i=1}^m (r_i-1)/2 \equiv (r_1r_2\cdots r_m-1)/2 \pmod 2$.
\item[(b)] $\sum_{i=1}^m (r_i^2-1)/8 \equiv (r_1^2r_2^2\cdots r_m^2 -1)/8 \pmod 2$.
\end{enumerate}
\it}
\begin{proof} Let ${\cal P}(m)$ the proposition defined by
$${\cal P}(m) \iff \sum_{i=1}^m (r_i-1)/2 \equiv (r_1r_2\cdots r_m-1)/2 \pmod 2.$$
Then ${\cal P}(1)\iff (r_1-1)/2 \equiv (r_1-1)/2 \pmod 2$ is true, and ${\cal P}(2)$ is part (a) of the lemma. If we make the induction hypothesis ${\cal P}(m)$, then
\begin{align*}
\sum_{i=1}^{m+1} (r_i-1)/2 &= \sum_{i=1}^m (r_i-1)/2 + (r_{m+1} -1)/2\\
&\equiv (r_1r_2\cdots r_m-1)/2 + (r_{m+1} -1)/2 \pmod 2\\
&\equiv (r_1r_2\cdots r_m r_{m+1}-1)/2 \pmod 2,
\end{align*}
where the last congruence is a consequence of the part (a) of the Lemma : the induction is completed, and ${\cal P}(m)$ is true for all $m\geq 1$.

The proof of part (b) is similar.
\end{proof}

\paragraph{Ex. 5.18}

{\it Let $D$ be a square-free integer that is also odd and positive. Show that there is an integer $b$ prime to $D$ such that $(b/D) = -1$.
}

\begin{proof}
Let $D = p_1p_2\cdots p_k$, where the $p_i$ are distinct odd primes.

Let $s$ be a nonresidue modulo $p_k$. By the Chinese Remainder Theorem, as $p_i \wedge p_j = 1$ if $i\ne j$,  there exists an integer $b$ such that
$$b \equiv 1 \pmod {p_1}, b \equiv 1 \pmod {p_2},\cdots, b \equiv 1 \pmod {p_{k-1}}, b \equiv s \pmod {p_k}.$$
Then $(b/p_i) = 1,\ i=1,2,\ldots k-1$, $(b/p_{k}) = -1$, so $b\wedge p_i = 1$ for all $i = 1,2,\ldots,k$. Then $b\wedge D = b\wedge p_1\cdots p_k = 1$ , and 
$$\legendre{b}{D} = \prod_{i=1}^k \legendre {b}{p_i} = \legendre{b}{p_k} = -1.$$
\end{proof}

\paragraph{Ex. 5.19}

{\it  Let $D$ be as in Exercise 18. Show that $\sum (a/D) = 0$, where the sum is over a reduced residue system modulo $D$. Conclude that exactly one half of the elements in $U(\Z/D\Z)$ satisfy $(a/D) = 1$.
}

\begin{proof}
Let $b$ such that $(b/D) = -1$ and $b \wedge D = 1$ : the existence of $b$ comes from Ex 5.18.

Let $S = \sum_{a\in A} (a/D)$, where $A$ is reduced residue system modulo $D$. As two reduced system modulo $D$ represent the same elements in $U(\Z/D\Z)$, the sum is independent of the  reduced residue system $A$ : we can write $$S = \sum_{\overline{a} \in U(\Z/D\Z)} (a/D).$$

 As $b \wedge D = 1$, we know from Ex. 3.6 that $B = bA = \{ba \ \vert \ a \in A\}$ is also a reduced system modulo $D$. In other words, the application  $U(\Z/D\Z) \to U(\Z/D\Z), \overline{a} \mapsto  \overline{a}\overline{b}$ is a bijection, so
$$\legendre{b}{D} S = \sum_{\overline{a} \in U(\Z/D\Z)} \legendre{b}{D} \legendre{a}{D}  =  \sum_{\overline{a} \in U(\Z/D\Z)} \legendre{ba}{D} = \sum_{\overline{c} \in U(\Z/D\Z)} \legendre{c}{D} = S  \qquad (\overline{c} = \overline{a}\overline{b}).$$


As $(b/D) = -1$, $-S = S $, so $S=0$.

Since $(a/D) = \pm 1$, one half of the elements in $U(\Z/D\Z)$ satisfy $(a/D) = 1$, and one half of the elements in $U(\Z/D\Z)$ satisfy $(a/D) =-1$.
\end{proof}

\paragraph{Ex. 5.20}

{\it (continuation) Let $a_1, a_2, \ldots, a_{\phi(D)/2}$ be integers between $1$ and $D$ such that $(a_i, D) = 1$ and $(a_i/D) = 1$. Prove that $D$ is a quadratic residue modulo a prime $p \not | \; D$, $p \equiv 1 \pmod 4$ iff $p \equiv a_i \pmod D$ for some $i$.
}

\begin{proof}
From Ex. 5.19 we know that there exist exactly $\phi(D)/2$ integers $a_i$ between $1$ and $D$ such that $a_i \wedge D = 1$ and $(a_i/D)= 1$. So $\{\overline{a_1},\ldots,\overline{a_{\phi(D)/2}}\}$ is the set of all $\overline{a} \in U(\Z/D\Z)$ such that $ (a/D) = 1$.

Let $D = p_1p_2\cdots p_k$, with distinct $p_i$, and $p$ a prime number, $p\equiv 1 \pmod 4, p \not \in \{p_1,\ldots,p_k\}$ (so $p = 4k+1, k \in \N$).

($\Leftarrow$)  Suppose that  $p \equiv a_i$ for some $i,\ 1\leq i \leq \phi(D)/2$, then $(p/D) = (a_i/D) = 1$, so (Prop. 5.2.2)
$$\legendre{D}{p} = (-1)^{\frac{p-1}{2} \frac{D-1}{2}} \legendre {p}{D} = (-1)^{2k\left(\frac{D-1}{2}\right)} \legendre {p}{D} = \legendre {p}{D} = 1 .$$

($\Rightarrow$) Suppose that $D$ is a quadratic residue modulo $p$. Then $(D/p) = 1$, so 
$$\legendre{p}{D} = (-1)^{\frac{p-1}{2} \frac{D-1}{2}} \legendre {D}{p} = 1.$$
Thus $\overline{p} \in \{\overline{a_1},\ldots,\overline{a_{\phi(D)/2}}\}$ since $\{\overline{a_1},\ldots,\overline{a_{\phi(D)/2}}\}$ is the set of all $\overline{a} \in U(\Z/D\Z)$ such that $ (a/D) = 1$.
Consequently $p \equiv a_i \pmod D$ for some $i$.
\end{proof}

\paragraph{Ex. 5.21}

{\it  Apply the method of Ex. 5.19 and 5.20 to find those primes for which $21$ is a quadratic residue.
}

\begin{proof}
Let $D = 21 = 3 \times 7$ ($D$ is positive, odd and square-free). We first search the $\phi(D)/2 = 6$ integers $a, \ 1\leq a \leq 21$, such that $ (a/D) = 1$.
$$\legendre{a}{21} = 1 \iff \legendre{a}{3} = \legendre{a}{7}=1 \ \mathrm{or}\  \legendre{a}{3} = \legendre{a}{7}=-1.$$
The first case is equivalent to $a\equiv 1 \pmod 3, a\equiv 1,2,4 \pmod 7$, that is $a\equiv 1,16,4 \pmod {21}$.

The second case gives $a \equiv -1 \pmod 3, a \equiv -1,-2,-4 \pmod 7$,  that is $a \equiv -1,-16,-4\pmod {21}$, or equivalently $a \equiv 20,5,17 \pmod{ 21}$.

So $A = \{1,4,5,16,17,20\}$ is the set of the integers $a$ such that $1 \leq a \leq 21$, $(a/D)=1$.

As $(21/3) = (21/7) = 0$, $21$ is not a quadratic residue modulo $3$ or $7$.

$\bullet$ $p \equiv 1 \pmod 4$.

From Ex.5.20, we know that $D=21$ is a quadratic residue modulo an odd prime $p$, $p\neq 3, p\neq 7$, $p \equiv 1 \pmod {4}$, iff $p \equiv a \pmod D$ for some $a\in A$.

$\bullet$ $p \equiv -1 \pmod 4$.

As $D = 21 \equiv 1 \pmod 4$, $\legendre{D}{p} \legendre{p}{D} = (-1)^{\frac{p-1}{2}\frac{D-1}{2}} = 1$, so the same reasoning as in Ex. 5.20 show that $D$ is a quadratic residue modulo $21$ iff $p \equiv a, a \in A$.

Conclusion : $21$ is a quadratic residue for $2$, and for the primes $p$ such that $$p \equiv 1,4,5,16,17,20 \pmod {21}.$$
\end{proof}

\paragraph{Ex. 5.22}

{\it Use the Jacobi symbol to determine $(113/997)$, $(215/761)$, $(514/1093)$, and $(401/757)$.
}

\begin{proof}
$(113/997) = (997/113) = (93/113) = (113/93) = (20/93) = (2^2/93)(5/93) = (5/93) = (93/5) = (3/5) =(5/3) = (2/3) = -1$.

\medskip

$(215/761) = (761/215) = (116/215) = (2^2/215)(29/215) = (29/215) = (215/29) = (12/29) = (2^2/29)(3/29) = (3/29) = (29/3) = (2/3) = -1$.

\medskip

$(514/1093) = (2/1093)(257/1093) = - (257/1093) = -(1093/257) = -(65/257) = -(257/65) = -(62/65) = -(2/65) (31/65) = -(31/65) = -(65/31) = - (3/31) = (31/3) = (1/3) = 1$.

\medskip

$(401/757) = (757/401) = (356/401) = (401/89) = (45/89) = (89/45) = (44/45) = (2^2/45) (11/45) = (11/45) = (45/11) = (1/11) = 1$.
\end{proof}

\paragraph{Ex. 5.23}

{\it Suppose that $p \equiv 1 \pmod 4$. Show that there exist integers $s$ and $t$ such that $pt = 1 + s^2$.  Conclude that $p$ is not a prime in $\Z[i]$. Remember that $\Z[i]$ has unique factorization.
}

\begin{proof}
As  $p \equiv 1 \pmod 4$, then $\legendre{-1}{p} = (-1)^{\frac{p-1}{2}} = 1$, thus $-1$ is a square modulo $p$.
 
 So  $-1 \equiv s^2 \pmod p,  s \in \mathbb{Z}$. Therefore
  there exist $s \in \mathbb{Z}, t \in \mathbb{Z}$ such that $pt = 1+s^2$.
 
In $\mathbb{Z}[i]$, $p \vert (s+i)(s-i)$.

 If $p$ was a prime in $\mathbb{Z}[i]$, then  $p \mid s+i$ ou $p \mid s-i$.
  
 This implies $s \pm i = (a+bi)p, (a,b) \in \mathbb{Z}^2$, thus $\pm1 = b p , p\mid 1$ : it's impossible.
 
Conclusion : if $p \equiv 1\pmod 4$, $p$ is not a prime in  $\mathbb{Z}[i]$.
\end{proof}

\paragraph{Ex. 5.24}

{\it If $p \equiv 1 \pmod 4$, show that $p$ is a sum of two squares, i.e. $p = a^2 + b^2$ with $a, b \in \Z$.(Hint : $p = \alpha \beta$, with $ \alpha$ and $\beta$ being non units in $\Z[i]$. Remember that $\Z[i]$ has unique factorisation.)
}

\begin{proof}
$\Z[i]$ is a principal ideal domain, thus  $p$ is prime in $ \Z[i]$  iff $p$ is irreducible in $ \Z[i]$.
 
If $p \equiv 1\pmod 4$, $p$ is not a prime by Ex.5.23, so it is not irreducible. Therefore
$p = \alpha \beta, \ \alpha,\beta \in \mathbb{Z}[i]$, where $\alpha, \beta$ are not units, so that $N(\alpha)>1, N(\beta)>1$ (where $N(a+bi) = a^2 + b^2$ is the complex norm).

$N(p) = p^2=  N(u) N(v), 1 < N(u) < p^2$

Thus $N(u) = p$, that is  $p = a^2+b^2$, where $u = a+bi$.

Conclusion : if $p$ is prime in $\mathbb{N}$, $p \equiv 1\pmod 4$, then $p = a^2+b^2,\ a,b \in \Z$, $p$ is a sum of two squares.

\end{proof}

\paragraph{Ex. 5.25}

{\it An integer is called a biquadratic residue modulo $p$ if it is congruent to a fourth power. Using the identity $x^4 + 4 = ((x + 1)^2 + 1)((x - 1)^2 + 1)$ show that $-4$ is a biquadratic residue modulo $p$ iff $p \equiv 1 \pmod 4$.
}

\begin{proof}
 
 $x^4+4 = (x^4 + 4 x^2 + 4) - 4 x^2 = (x^2+2)^2 - 4x^2 = (x^2 + 2 -2x)(x^2+2+2x) $, so
 
 $$x^4+4 = ((x-1)^2+1)((x+1)^2+1).$$
 
 If $-4 \equiv x^4\  [p]$ for some $x \in \Z$, then $p \mid (x+1)^2 + 1$ or $p \mid (x-1)^2+1$
 
In the two cases, $-1$ is a quadratic residue modulo $p$, thus $\legendre{-1}{p} = 1 : p \equiv 1\  [4]$.
 

 
 Conversely, if $p\equiv 1\ [4], \legendre{-1}{p} = 1 $, then it exists an integer $a$ such that $-1 \equiv a^2 \ [p]$.
 
Let  $x = a-1$. Then $p \mid (x+1)^2 +1$, thus $p \mid x^4+4$ : $-4$ is a biquadratic residue modulo $p$.
 
 Conclusion : $$\exists x \in \mathbb{Z},\  x^4 \equiv -4 \ [p] \iff p \equiv 1\ [4].$$
\end{proof}

\paragraph{Ex. 5.26}

{\it This exercise and Ex. 5.27 and 5.28 give Dirichlet's beautiful proof that $2$ is a biquadratic residue modulo $p$ iff $p$ can be written in the form $A^2 + 64B^2$ , where $A, B \in \Z$. Suppose that $p \equiv 1 \pmod 4$. Then $p = a^2 + b^2$ by Ex. 5.24. Take $a$ to be odd.  Prove the following statements:

\begin{enumerate}
\item[(a)]$(a/p) = 1$.
\item[(b)] $((a + b)/p) = (-1)^{((a+b)^2 -1)/8}$.
\item [(c)] $(a + b)^2 \equiv 2ab \pmod p$
\item[(d)] $(a + b)^{(p- 1)/2} \equiv (2ab)^{(p- 1)/4} \pmod p$.
\end{enumerate}
}

\begin{proof}
Let $p$ a prime number, $p \equiv 1\  [4]$ : $p = 4k+1, k \in \mathbb{N}^*$.
  
Then  $p = a^2 + b^2$ (Ex. 5.24).
  
  As $a,b$ are not of the same parity, up to exchange $a$ and $b$, we will suppose that $a$ is odd (then  $b$ is even).
  
  (a) $$\legendre{a}{p} \equiv a^{\frac{p-1}{2}} = a^{2k} \ [p].$$
  
  Using the law of quadratic reciprocity for Jacobi's symbol (Proposition 5.2.2), where $a,p$ are odd numbers :
  
  $$\legendre{a}{p} = \legendre{p}{a} (-1)^{\frac{p-1}{2} \frac{a-1}{2}} = \legendre{p}{a},$$ since $p \equiv1 \ [4]$.
  
 If  $a = p_1 p_2 \cdots p_l$ is the decomposition of $a$ in prime factors, with not necessarily distinct primes , then
  
  $$\legendre{p}{a} = \legendre {p}{p_1}  \legendre {p}{p_2}\cdots \legendre {p}{p_l}.$$
  
Since $p = a^2+b^2$, $p \equiv b^2 \ [p_i]$, thus $\legendre {p}{p_i} = 1$ for all $i$.
  
  $$\legendre{a}{p} = \legendre{p}{a}=1.$$
  
   \vspace{0.5cm}
   (b) $a+b$ is odd, and $p \equiv 1 \ [4]$, thus
   
   $$\legendre{a+b}{p} = \legendre{p}{a+b} =\legendre{2^2 p}{a+b}= \legendre{2}{a+b} \legendre{2p}{a+b}.$$
  
 If $a+b = q_1 q_2 \cdots q_l$, as $2p = (a+b)^2 +(a-b)^2$,
   $2p \equiv (a-b)^2 \ [q_i]$, thus $\legendre {2p}{q_i}=1$.
  
  $$\legendre{2p}{a+b} = \legendre{2p}{q_1} \cdots \legendre {2p}{q_l} = 1.$$
  
  Moreover $\legendre {2}{a+b} = (-1)^{\frac{(a+b)^2-1}{8}}$, so
  
$$\legendre{a+b}{p} = (-1)^{\frac{(a+b)^2-1}{8}}.$$
  
     \vspace{0.5cm}
     (c) $(a+b)^2 = a^2 + b^2 + 2ab = p + 2ab \equiv 2ab \ [p]$
     
       \vspace{0.5cm}
       (d)$[(a+b)^2]^{\frac{p-1}{4}} \equiv (2ab)^{\frac{p-1}{4}} \ [p]$, thus
       $$(a+b)^{\frac{p-1}{2}} \equiv (2ab)^{\frac{p-1}{4}} \ [p].$$
\end{proof}

\paragraph{Ex. 5.27}

{\it Suppose that $f$ is such that $b \equiv af \pmod p$. Show that $f^2 \equiv -1 \pmod p$, and that $2^{(p-1)/4} \equiv f^{ab/2} \pmod p$.
}

\begin{proof}
 Let $f$ such as $b \equiv af \ [p]$.
 
This is equivalent to $\overline{f} = \overline{b} \overline{a}^{-1}$ in $\mathbb{F}_p^*$.
 
As $\overline{a}^2 = - \overline{b}^2$, $\overline{f}^2 = -\overline{1}$, so that $f^2 \equiv -1 \ [p]$.
 
We deduce from Ex. 5.26 (d) and (b) that
 \begin{align*}
 (2ab)^{\frac{p-1}{4}} &\equiv (a+b)^{\frac{p-1}{2}} = \legendre{a+b}{p}\\
 &\equiv (-1) ^{\frac{(a+b)^2 - 1}{8}}\ \\
 &\equiv (f^2)^{\frac{(a+b)^2 - 1}{8}}\\
 &\equiv f ^{\frac{(a+b)^2 - 1}{4}} = f^{\frac{a^2+b^2-1 +  2ab}{4}}\\
 &\equiv f^{\frac{p-1}{4}} f^{\frac{ab}{2}} \pmod p
 \end{align*}
Since $a^{\frac{p-1}{2}} = \legendre{a}{p} = 1$ by Ex. 5.26(a)),  
then $$(ab)^{\frac{p-1}{4}} \equiv (a^2 f)^{\frac{p-1}{4}} \equiv a^{\frac{p-1}{2}} f^{\frac{p-1}{4}}\equiv  f^{\frac{p-1}{4}} \ [p],$$
so $$2^{\frac{p-1}{4}} f^{\frac{p-1}{4}} \equiv f^{\frac{ab}{2}}f^{\frac{p-1}{4}}\ [p].$$
As $f^{\frac{p-1}{4}} \not \equiv 0 \ [p]$,
$$2^{\frac{p-1}{4}} \equiv f ^{\frac{a b }{2} }\ [p].$$
\end{proof}

\paragraph{Ex. 5.28}

{\it Show that $x^4 \equiv 2 \pmod p$ has a solution for $p \equiv 1 \pmod 4$ iff $p$ is of the form $A^2 + 64B^2$.
}

\begin{proof}
If  $p\equiv 1\ [4]$ and if there exists $x \in \mathbb{Z}$ such that $x^4 \equiv 2\ [p]$, then
$$2^{\frac{p-1}{4} }\equiv  x^{p-1} \equiv 1 \ [p].$$ 

From Ex. 5.27, where $p = a^2 +b^2, a$ odd,  we know that $$f^{\frac{ab}{2}} \equiv 2^{\frac{p-1}{4} } \equiv 1 \ [p].$$

Since $f^2 \equiv -1\ [p]$, the order of $f$ modulo $p$ is 4, thus $4 \mid \frac{ab}{2}$, so $8\mid ab$.

As $a$ is odd, $8 | b$, then $p = A^2 + 64 B^2$ (with $A = a, B = b/8$).

\bigskip

Conversely, if $p=A^2+64 B^2$, then $p\equiv A^2 \equiv 1 \ [4]$.

Let $a=A,b=8B$. Then $$2^{\frac{p-1}{4} } \equiv f^{\frac{ab}{2}} \equiv f^{4AB} \equiv (-1)^{2AB} \equiv 1 \ [p].$$

As $2^{\frac{p-1}{4} } \equiv 1 \ [p]$, $x^4 \equiv 2 \ [p]$ has a solution in $\Z$ (Prop. 4.2.1), i.e. $2$ is a biquadratic residue modulo $p$.

Conclusion : 

$$\exists A \in \mathbb{Z}, \exists B \in \mathbb{Z}\,, p = A^2+64 B^2 \iff( p\equiv 1 \ [4] \ \mathrm{and} \ \exists x \in \mathbb{Z}, \, x^4 \equiv 2 \ [p]).$$

\vspace{0.5cm}
Note  : the equation $x^4 \equiv 2\ [p]$ has also solutions if $p \equiv -1 \ [8]$.

Indeed, the equation $x^4 \equiv 2 \ [p]$ has a solution in $\Z$  iff $2^{\frac{p-1}{d}} = 1$, where $d = 4 \wedge (p-1) = 2$, thus  iff $2^{\frac{p-1}{2}} \equiv 1 \ [p]$, which is true since $\legendre{2}{p}=1$.

For instance, $8^4 \equiv 2 \pmod {23}$, with $23\equiv -1 \pmod 8$.
\end{proof}

\paragraph{Ex. 5.29}

{\it Let $(RR)$ be the number of pairs $(n, n + 1)$ in the set $1,2,3,\ldots, p - 1$ such that $n$ and $n + 1$ are both quadratic residues modulo $p$. Let $(NR)$ be the number of pairs $(n, n + 1)$ in the set $1,2,3, \ldots, p - 1$ such that $n$ is a quadratic nonresidue and $n + 1$ is a quadratic residue. Similarly, define $(RN)$ and $(NN)$. Determine the sums $(RR) + (RN)$, $(NR) + (NN)$, $(RR) + (NR)$, and $(RN) + (NN)$.
}

\begin{proof}
Let $E$ be the set of pairs $(n,n+1)\in \N^2, 1 \leq n \leq p-2$. Then $\vert E \vert = p-2$.  

Write $RR$ the set of pairs $(n,n+1)$ such that $n$ and $n+1$ are both a quadratic residues, and $(RR) = \vert RR \vert$ its cardinality, and similar definitions for $RN,NR,NN$.

As $E = RR \cup RN \cup NR \cup NN$ (disjoint union), 
$$(RR) +(RN) + (NR)+ (NN) = \vert E \vert = p-2.$$

$\bullet$ $RR \cup RN$ is the set of pairs $(n,n+1)$ in $E$ such that $n$ is a residue. Its cardinality is the number of residues in $[1,p-2]$, thus is the number of residues in $[1,p-1]$, minus $s$, where $s = 1$ if $p-1$ is a residue, $s=0$ otherwise. In both cases $p \equiv 1,3 \pmod 4$, $s = \frac{1+(-1)^{\frac{p-1}{2}}}{2}$, and the total number of residues is $(p-1)/2$, so
$$(RR)+(RN) = \frac{p-1}{2} -s = \frac{p-1}{2} -\frac{1+(-1)^{\frac{p-1}{2}}}{2} = \frac{1}{2}(p - 2 - (-1)^{\frac{p-1}{2}}).$$

$\bullet$ Similarly, $(NR)+(NN)$ is the number of nonresidues in $[1,p-1]$, minus $t$, where $t=1$ if $p-1$ is a nonresidue, $t=0$ otherwise : $t =\frac{1-(-1)^{\frac{p-1}{2}}}{2}$, so
$$(NR)+(NN) = \frac{1}{2}(p - 2 + (-1)^{\frac{p-1}{2}})$$
(the sum of these two results is indeed $p-2 = \vert E \vert$).

$\bullet$ As $1$ is a residue, $(RR)+(NR)$ is the number of residues in $[1,p-1]$, minus $1$ :
$$(RR)+(NR) = \frac{p-1}{2} - 1.$$

$\bullet$ $(RN)+(NN)$ is the number of nonresidues in $[2,p-1]$, equal to the number of residues in $[1,p-1]$ :
$$(RN)+(NN) = \frac{p-1}{2}.$$
\end{proof}

\paragraph{Ex. 5.30}

{\it Show that $(RR) + (NN) - (RN) - (NR) = \sum_{n=1}^{p-1}(n(n+1)/p)$. Evaluate this sum and show that it is equal to $-1$. (Hint : The result of Exercise 8 is useful.)
}

\begin{proof}
Let $\chi$ be  the characteristic function of $RR \cup NN$ : if $1 \leq n \leq p-1$,
$\chi(n) = 1$ if $n,n+1$ are both  residues, or if $n,n+1$ are both non residues. Then 
$$\chi(n) = \frac{1}{2} \left( 1 + \legendre{n}{p} \legendre{n+1}{p} \right) $$
(if $\chi(n) = 1, \legendre{n}{p} \legendre{n+1}{p} = 1$, and $\legendre{n}{p} \legendre{n+1}{p} = -1$ otherwise.)

Similarly, let $\chi'$ the characteristic function of $RN \cup NR$ : $\chi'(n) =1$ if exactly one of the integer $n,n+1$ is a residue, $0$ otherwise. Then 
$$\chi'(n) = \frac{1}{2} \left( 1 - \legendre{n}{p} \legendre{n+1}{p} \right).$$
As each integer $n$ between $1$ and $p-1$ brings the contribution $1$ if $n \in RR \cup NN$, and $-1$ if $n \in RN \cup NR$, then
\begin{align*}
(RR) + (NN) - (RN) - (NR) &= \sum_{n=1}^{p-1} (\chi(n) - \chi'(n))\\
&= \frac{1}{2} \sum_{n=1}^{p-1}  \left( 1 + \legendre{n(n+1)}{p}  \right)  - \left( 1 - \legendre{n(n+1)}{p}  \right) \\
&= \sum_{n=1}^{p-1}   \legendre{n(n+1)}{p}  
\end{align*}
To evaluate this sum $S$, note that $4n(n+1) = (2n+1)^2 - 1$, thus
$$S = \sum_{n=1}^{p-1}   \legendre{n(n+1)}{p} = \sum_{n=1}^{p-1}   \legendre{4n(n+1)}{p} = \sum_{n=1}^{p-1}   \legendre{(2n+1)^2 - 1}{p}.$$
This sum can be written $ S = \sum_{\overline{n} \in \F_p^*} ((2n+1)^2 - 1)/p)= \sum_{\overline{n} \in \F_p} ((2n+1)^2 - 1)/p)$, since $(0/p) = 0$.
As $f : \F_p \to \F_p, \overline{n} \mapsto (2\overline{n}+1)$ is a bijection ($2$ is invertible in $\F_p^*$),
$$\sum_{\overline{n} \in \F_p} \legendre{(2n+1)^2 - 1}{p}  = \sum_{\overline{y} \in \F_p} \legendre{y^2 - 1}{p}\qquad (y = 2n+1).$$
As $p \nmid 1$, the evaluation of this last sum is given in Exercise 5.8 : $S = -1$, so 
$$ (RR) + (NN) - (RN) - (NR)  = \sum_{n=1}^{p-1}   \legendre{n(n+1)}{p}  = -1.$$
\end{proof}

\paragraph{Ex. 5.31}
{\it Use the results of Exercises 29 and 30 to show that $(RR) = \frac{1}{4}(p-4-\varepsilon)$, where $\varepsilon = (-1)^{(p-1)/2}$
}

\begin{proof}
To summarize the results of the Ex. 5.29 and 5.30,
\begin{align*}
(a) (RR) +(RN) + (NR)+ (NN) &=  p-2\\
(b) (RR) + (NN) - (RN) - (NR)  &= -1\\
\end{align*}
and
\begin{align*}
(c)(RR)+(RN) &=\frac{1}{2}\left(p - 2 - (-1)^{\frac{p-1}{2}}\right)\\
(d)(RR)+(NR) &= \frac{p-1}{2} - 1\\
\end{align*}
The sum of (a) and (b) gives
$$(e) (RR) + (NN) = \frac{p-3}{2}.$$
The sum of (c),(d),(e) gives (using (a))
$$2(RR) + p-2 = \frac{p-2}{2} + \frac{p-1}{2} + \frac{p-3}{2} - 1 - \frac{(-1)^{\frac{p-1}{2}}}{2},$$
so
$$2 (RR) = \frac{p-1}{2} + \frac{p-3}{2} - \frac{p-2}{2} - 1 - \frac{(-1)^{\frac{p-1}{2}}}{2} = \frac{p}{2} - 2 - \frac{(-1)^{\frac{p-1}{2}}}{2},$$
$$(RR) = \frac{1}{4} (p-4-\varepsilon),\ \mathrm{where} \ \varepsilon = (-1)^{\frac{p-1}{2}}.$$
\end{proof}

\paragraph{Ex. 5.32}

{\it If $p$ is an odd prime, show that $(2/p) = \prod_{j=1}^{(p-1)/2} 2\cos(2 \pi j/p)$. Use this to give another proof to Proposition 5.1.3.
}

\begin{proof}
Let $p$ be an odd prime number, and $\zeta = e^{2i\pi/p}$. Then $\zeta^p = 1$.

Let $$P = \prod_{j=0}^{p-1} (\zeta^j + \zeta^{-j})= \prod_{j=0}^{p-1} 2 \cos(2\pi j/p).$$
\begin{align*}
P &= \zeta^0\zeta^{-1}\cdots\zeta^{-(p-1)} \prod_{j=0}^{p-1} (\zeta^{2j} + 1)\\
&= (\zeta^p)^{-(p-1)/2} \prod_{j=0}^{p-1} (\zeta^{2j} + 1)\\
&= \prod_{j=0}^{p-1} (\zeta^{2j} + 1)
\end{align*}
As $\zeta^j$ depends only of the class $\overline{j} \in \F_p$, this product can be written 
$$P = \prod_{\overline{j }\in \F_p} (\zeta^{2j} + 1) = \prod_{\overline{k} \in \F_p} (\zeta^{k} + 1)\qquad (k=2j), $$
since $f : \F_p \to \F_p, x \mapsto 2x$ is a bijection. So
$$P = \prod_{k=0}^{p-1} (\zeta^{k} + 1).$$
Since $\zeta^0 = 1, \zeta,\cdots, \zeta^{p-1}$ are the roots of the polynomial $f(x) = x^p-1$, then $1+\zeta^0, \cdots,1+\zeta^{p-1}$ are the roots of $g(x) =(x-1)^p - 1 = f(x-1)$, so $g(x) = \prod_{k=0}^{p-1} (x - (1+\zeta^k))$. 

As $g(0) = (-1)^p - 1 = -2 = (-1-\zeta^0)\cdots(-1-\zeta^{p-1}) = -\prod_{k=0}^{p-1} (\zeta^{k} + 1)$, we obtain
$$P = \prod_{j=0}^{p-1} 2 \cos(2\pi j/p) = \prod_{k=0}^{p-1} (\zeta^{k} + 1) = 2,$$
so
$$\prod_{j=1}^{p-1} 2 \cos(2\pi j/p)  = 1.$$
\begin{align*}
1 &= \prod_{j=1}^{p-1} 2 \cos(2\pi j/p)\\
&=\prod_{j=1}^{(p-1)/2} 2 \cos(2\pi j/p) \prod_{j=(p+1)/2}^{p-1} 2 \cos(2\pi j/p)\\
&= \prod_{j=1}^{(p-1)/2} 2 \cos(2\pi j/p)  \prod_{k = 1}^{(p-1)/2} 2 \cos(2\pi - 2\pi k/p) \qquad (k = p-j) \\
\end{align*}
As $\cos(2\pi - \alpha) = \cos(\alpha)$, 
$$1 = \left ( \prod_{j=1}^{(p-1)/2} 2 \cos(2\pi j/p)  \right)^2, \ \mathrm{so} \ \prod_{j=1}^{(p-1)/2} 2 \cos(2\pi j/p) = \pm 1$$

\begin{enumerate}
\item[$\bullet$] Case 1: if $1\leq j \leq p/4, 0 \leq 2\pi j/p <\pi/2$, thus $\cos (2\pi j/p)>0$.

\item[$\bullet$] Case 2: if $p/4<j\leq (p-1)/2, \pi/2 < 2\pi j/p < \pi$, thus $\cos (2\pi j/p)<0$.
\end{enumerate}
In the first case, $2 \leq 2j \leq (p-1)/2$ : the least residue of $2j$ is positive. In the second case $ p/2< 2j \leq p-1$ : the least residue of $2j$ is negative.

Let $\mu$ be the number of negative least residues of the integer $2j,\ 1 \leq j \leq (p-1)/2 $. We know from Gauss' Lemma that $(2/p) = (-1)^\mu$. As $\mu$ is also the number of $j,\ 1 \leq j \leq (p-1)/2$ such that $\cos (2\pi j/p)<0$,
$$ \prod_{j=1}^{(p-1)/2} 2 \cos(2\pi j/p) = (-1)^\mu = \legendre{2}{p}.$$

If $p \equiv 1\ [8]$ , $p = 8q +1, q \in \N$. For $1 \leq j \leq (p-1)/2$,

$$\cos (2\pi j/p) < 0 \iff p/4\leq j \leq (p-1)/2 \iff 2q +1 \leq j \leq 4q,$$ so $\mu =2q$ and $(2/p) = (-1)^\mu = 1$.

If $p\equiv -1 \ [8]$, $p = 8q - 1, q \in \N^*$.
$$\cos (2\pi j/p) < 0 \iff p/4\leq j \leq (p-1)/2 \iff 2q \leq j \leq 4q -1,$$
 thus $\mu =2q$ and $(2/p) = (-1)^\mu = 1$.
 
 If $p \equiv 3 \ [8]$, $p = 8q + 3, q \in \N$.
 $$\cos (2\pi j/p) < 0 \iff p/4\leq j \leq (p-1)/2 \iff 2q + 1 \leq j \leq 4q +1,$$
  thus $\mu =2q+1$ and $(2/p) = (-1)^\mu = 1$.
  
  If $p \equiv -3 \ [8]$, $p = 8q - 3, q \in \N^*$,
  $$\cos (2\pi j/p) < 0 \iff p/4\leq j \leq (p-1)/2 \iff 2q  \leq j \leq 4q -2,$$
  thus $\mu =2q-1$ and $(2/p) = (-1)^\mu = 1$.
\end{proof}

\paragraph{Ex. 5.33}

{\it Use Proposition 5.3.2 to derive the quadratic character of $-1$.
}

\begin{proof}
Let $f(z) = e^{2\pi i z}- e^{-2\pi i z}$. If $p$ is an odd prime, $a \in \Z$, and $p\nmid a$, we know from Prop. 5.3.2 that
$$\prod_{l=1}^{(p-1)/2} f\left(\frac{la}{p} \right) = \legendre{a}{p} \prod_{l=1}^{(p-1)/2} f\left( \frac{l}{p} \right).$$
For $a = -1$, as $f(-z) = -f(z)$, 
\begin{align*}
\legendre{-1}{p} \prod_{l=1}^{(p-1)/2} f\left( \frac{l}{p} \right) &= \prod_{l=1}^{(p-1)/2} f\left(\frac{-l}{p} \right)\\
&=(-1)^{(p-1)/2} \prod_{l=1}^{(p-1)/2} f\left( \frac{l}{p} \right)
\end{align*}
Moreover $f(z) = 0 \iff e^{4\pi i z} = 1 \iff 4\pi i z = 2 k i \pi, k \in \Z \iff z = k/2, k\in \Z$, so, if $l \in \Z$,
$f\left( \frac{l}{p} \right) = 0 \iff l/p = k/2, k \in \Z \iff p \mid 2l \iff p \mid l$. For $1\leq l <p$, this is impossible, so $\prod_{l=1}^{(p-1)/2} f\left( \frac{l}{p} \right) \ne 0$. Consequently,
$$\legendre{-1}{p} = (-1)^{(p-1)/2}.$$
\end{proof}

\paragraph{Ex. 5.34}

{\it If $p$ is an odd prime distinct from $3$, show that 
$$\legendre{3}{p} = \prod_{j=1}^{(p-1)/2} \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right).$$
}

\begin{proof}
Let $p$ be an odd prime number, $p\ne 3$ and $\zeta= e^{2i\pi/p}$.
\begin{align*}
3 - 4 \sin^2\left(\frac{2\pi j}{p}\right) &= 3 - 4  \left( \frac{\zeta^j - \zeta^{-j}}{2i}\right)^2\\
&= 3 + \zeta^{2j} + \zeta^{-2j} - 2\\
&= 1 +\zeta^{2j} + \zeta^{-2j}\\
&= 1 + 2 \cos \left(\frac{4\pi j}{p} \right)
\end{align*}
(As $\cos(2\alpha) = 1 - 2 \sin^2\alpha$, so $3 - 4 \sin^2 \alpha = 1 + 2 \cos \alpha$.)

Let $$P = \prod_{j=1}^{p-1} \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right) =  \prod_{\overline{j} \in \F_p^*} \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right).$$
Since $f : \F_p^* \to \F_p^*$ defined by $\overline{j} \mapsto 2\overline{j}$ is a bijection,
\begin{align*}
P  &= \prod_{\overline{j} \in \F_p^*} \left(1 + \zeta^{2 j}+ \zeta^{-2j}\right)\\
&= \prod_{\overline{k} \in \F_p^*} \left(1 + \zeta^{k}+ \zeta^{-k}\right)\qquad (k = 2j).
\end{align*}
Therefore
\begin{align*}
P &=  \prod_{k=1}^{p-1} \zeta^{-k}\left(1 + \zeta^k + \zeta^{2k} \right)\\
&=  \prod_{k=1}^{p-1} \zeta^{-k} \  \frac{\prod_{k=1}^{p-1} (1 - \zeta^{3k})}{\prod_{k=1}^{p-1} (1 - \zeta^{k})}
\end{align*}
$\prod_{k=1}^{p-1} \zeta^{-k} =\left( \zeta^p\right)^{-(p-1)/2} = 1$. Moreover, $\prod_{k=1}^{p-1} (1 - \zeta^{3k}) = \prod_{k=1}^{p-1} (1 - \zeta^{k})$, since $\overline{k} \mapsto 3 \overline{k}$ is a bijection in $\F_p^*$, thus $P = 1$, and consequently
\begin{align*}
1 &= \prod_{j=1}^{p-1}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)\\
&=\prod_{j=1}^{(p-1)/2}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right) \prod_{j=(p+1)/2}^{p-1}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)\\
&= \prod_{j=1}^{(p-1)/2}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)  \prod_{k=1}^{(p-1)/2}  \left(3-4 \sin^2\left(\frac{2 \pi (p-k)}{p}\right)\right) \qquad (k=p-j)\\
&=\left [ \prod_{j=1}^{(p-1)/2}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)\right]^2
\end{align*}

Thus $\prod_{j=1}^{(p-1)/2}  \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)= \pm 1$.

Let $\nu$ be the number of negative factors in this product.

If $1 \leq j \leq (p-1)/2$, then $0 < 4\pi j/p < 2 \pi$.
\begin{align*}
3-4 \sin^2\left(\frac{2 \pi j}{p}\right)<0 &\iff 1 + 2 \cos \frac{4\pi j}{p} <0\\
 &\iff \cos \frac{4\pi j}{p} < \cos \frac{2\pi}{3}\\
&\iff \frac{2\pi}{3} < \frac{4 \pi j}{p} < \frac{4 \pi}{3}\\
&\iff \frac{p}{6} < j < \frac{p}{3}\\
& \iff \frac{p}{2} < 3j < p
\end{align*}
Let $\mu$ be the number of integers $j, 1 \leq j \leq (p-1)/2$ such that the least remainder of $3j$ is negative. Since $3 \leq 3j \leq 3 (p-1)/2$, these $j$ are the integers such that  $(p-1)/2 < 3j \leq p-1$, and since $3j \ne p/2$, such that $\frac{p}{2} < 3j < p$, so $\mu = \nu$.
Therefore
$$\prod_{j=1}^{(p-1)/2} \left(3-4 \sin^2\left(\frac{2 \pi j}{p}\right)\right)  =(-1)^\nu = (-1)^\mu = \legendre{3}{p}.$$
\end{proof}

\paragraph{Ex. 5.35}

{\it Use the preceding exercise to show that $3$ is a square modulo $p$ iff $p$ is congruent to $1$ or $-1$ modulo $12$.
}

\begin{proof}
We know from Ex. 5.34 that $\nu = \mathrm{Card}\, \{j \in [1,(p-1)/2] \ \vert \ p/2 \leq 3j < p\} = \mu$. 
Therefore $\nu$ is the number of $j$ such that $p/6 \leq j < p/3$, so $\nu =\lfloor p/3 \rfloor - \lfloor p/6 \rfloor $.

If $p = 12k +1$, $\nu = \lfloor p/3 \rfloor - \lfloor p/6 \rfloor = 4k - 2k = 2k :  (3/p) = (-1)^\nu = 1$.

If $p = 12k +5$, $\nu = \lfloor p/3 \rfloor - \lfloor p/6 \rfloor = 4k + 1 - 2k = 2k + 1:  (3/p) = (-1)^\nu = -1$.

If $p = 12k - 5$, $\nu = \lfloor p/3 \rfloor - \lfloor p/6 \rfloor = 4k - 2 - (2k-1) = 2k -1:  (3/p) = (-1)^\nu = -1$.

If $p = 12k  - 1$, $\nu = \lfloor p/3 \rfloor - \lfloor p/6 \rfloor = 4k  - 1 - (2k-1) = 2k :  (3/p) = (-1)^\nu = 1$.

Therefore $3$ is a square modulo $p$ (where $p\ne 2, p \ne 3$)  iff $p$ is congruent to $1$ or $-1$ modulo $12$.
\end{proof}

\paragraph{Ex. 5.36}

{\it Show that part (c) of Proposition 5.2.2 is true if $a$ is negative and $b$ is positive (both still odd).
}

\bigskip

As said by Adam Michalik, the Jacobi symbol $\legendre{a}{b}$ only defined for positive $b$, so the question, which concerns $\legendre{a}{b} \legendre{b}{a}, a<0$ makes no sense.

To give sense to this question, we must substitute the Kronecker symbol to the Jacobi symbol. The Kronecker symbol (not defined in Ireland-Rosen) is the usual extension of Jacobi symbol (see for instance [Henri Cohen] A course in computational algebraic number theory, [Henri Cohen] Number theory (vol. 1), or [Harvey Cohn] Advanced number theory).

We define Kronecker (or Kronecker-Jacobi) symbol $\legendre{a}{b}$ for any $a$ and $b$ in $\Z$ in the following way.
\begin{enumerate}
\item[(1)] If $b=0$, then $\legendre{a}{0} = 1$ if $a = \pm 1$, and$\legendre{a}{0} = 0$ otherwise.

\item[(2)] For $b \ne 0$, write $b = \prod p$, where the $p$ are not necessarily distinct primes (including $2$), or $p = -1$ to take care of the sign. Then we set
$$\legendre{a}{b} = \prod \legendre{a}{p},$$
where $\legendre{a}{p}$ is the Legendre symbol defined above for $p>2$, and where we define
$$\legendre{a}{2} = 
\begin{cases}
0 & \text{if $a$ is even}\\
(-1)^{(a^2-1)/8} &\text{if $a$ is odd,}
\end{cases}
$$
and also
$$\legendre{a}{-1} = 
\begin{cases}
1 & \text{if $a\geq 0$}\\
-1 & \text{if $a<0$}
\end{cases}
$$
\end{enumerate}
\begin{proof} 
Suppose that $a <0, b>0$, both odd. Let $a = -A,A>0, A = p_1p_2\cdots p_k$, where the $p_i$ are not necessarily distinct primes. Then
\begin{align*}
\legendre{a}{b}\legendre{b}{a} &= \legendre{-A}{b}\legendre{b}{-A} \\
\legendre{-A}{b} &= \legendre{-1}{b} \legendre{A}{b} 
=(-1)^{(b-1)/2} \legendre{A}{b}\\
\legendre{b}{-A} &= \legendre{b}{-1} \legendre{b}{p_1}\cdots \legendre{b}{p_k}
= \legendre{b}{A}.
\end{align*}
Therefore, by Prop. 5.2.2, as $A,b$ are odd and positive,
\begin{align*}
\legendre{a}{b}\legendre{b}{a} &= (-1)^{ \frac{b-1}{2} } \legendre{A}{b} \legendre{b}{A}\\
&=(-1)^{ \frac{b-1}{2} } (-1)^{\frac{A-1}{2}\frac{b-1}{2}}\\
&=(-1) ^{\frac{b-1}{2} [1 + \frac{-a-1}{2}]}\\
&=(-1)^{\frac{b-1}{2}\frac{1-a}{2} }\\
&=(-1)^{\frac{b-1}{2}\frac{a-1}{2} }\\
\end{align*}
So the law of quadratic reciprocity remains valid for the Kronecker symbol when $a$ is negative ($b>0$, $a,b$ both odd).
\end{proof}

\paragraph{Ex. 5.37}

{\it Show that if $a$ is negative, then $p \equiv q \pmod {4a}$, $p \nmid a$ implies $(a/p) = (a/q)$.
}

\begin{proof}
Write $a = -A, A>0$. As $p \equiv q \pmod {4a}$, we know from Prop. 5.3.3. (b) that $(A/p) = (A/q)$.

Moreover,
\begin{align*}
\legendre{a}{p}&= \legendre{-A}{p} = (-1)^{(p-1)/2} \legendre{A}{p}\\
\legendre{a}{q}&= \legendre{-A}{q} = (-1^{(q-1)/2} \legendre{A}{q}
\end{align*}
As  $p \equiv q \pmod {4a}$, $ p = q + 4ak, k\in \Z$, so
$$(-1)^{(p-1)/2} = (-1)^{(q+4ak-1)/2} = (-1)^{(q-1)/2},$$
so $(a/p) = (a/q)$.
\end{proof}

\paragraph{Ex. 5.38}

{\it Let $p$ be an odd prime. Derive the quadratic character of $2$ modulo $p$ by verifying the following steps, involving the Jacobi symbol:

$$
 \legendre{2}{p} = \legendre{8-p}{p} = \legendre{p}{p-8} = \legendre{8}{p-8} = \legendre{2}{p-8}.
$$

Generalize the argument to show that
$$
  \left(\frac{a}{p}\right) = \left(\frac{a}{p-4a}\right), \qquad a>0, p \nmid a.
$$
}
(As in Ex. 5.36, since $8 - p$ or $p-8$ is negative, we interpret $(a/b)$ as the Kronecker symbol : see definition in Ex. 5.36.)
\begin{proof}
As $(2^2/p) = 1$ and $8-p \equiv 8 \pmod p$,
$$ \legendre{2}{p} = \legendre{2^2}{p} \legendre{2}{p} = \legendre{8}{p} = \legendre{8-p}{p}.$$
As $p$ and $8-p$ are odd numbers and $p>0$, from the extension of the law of quadratic reciprocity to $a<0$ proved in Ex. 5.36, we obtain
$$\legendre{8-p}{p} = (-1)^{\frac{7-p}{2} \frac{p-1}{2}} \legendre{p}{8-p}.$$
Moreover
\begin{align*}
(7-p)(p-1) &\equiv (-1-p)(p-1) = 1 - p^2 \pmod 8\\
\end{align*}
As $p= 2k+1$ is odd, $p^2 = 4k^2+4k+1 = 8 \frac{k(k+1)}{2} + 1 \equiv 1 \pmod 8$, so $(7-p)(p-1) \equiv 0 \pmod 8$ and $\frac{7-p}{2} \frac{p-1}{2}$ is even, so
$$\legendre{8-p}{p} = \legendre{p}{8-p}.$$
As $p>0$, $\legendre{p}{-1} = 1$, thus $ \legendre{p}{8-p} = \legendre{p}{-1}  \legendre{p}{p-8} = \legendre{p}{p-8}$ (with the same argument, this is also true for the  3 odd primes such that $8-p>0$), so
$$\legendre{8-p}{p} = \legendre{p}{p-8}.$$
\end{proof}
As $p\equiv 8 \pmod{p-8}$, $\legendre{p}{p-8}  = \legendre{8}{p-8}$, and since $8 = 2^2\times 2$, $\legendre{8}{p-8} = \legendre{2}{p-8}$. We have proved for all odd primes $p$ that
$$  \legendre{2}{p} = \legendre{8-p}{p} = \legendre{p}{p-8} = \legendre{8}{p-8} = \legendre{2}{p-8}.$$

The preceding arguments remain valid if we replace the odd prime $p$ by any odd positive integer.  So with an immediate induction, we see that for all $k \in \N$,
$$ \legendre{2}{p} = \legendre{2}{p-8k}.$$
So the quadratic character of $2$ modulo $p$ depends only of the class of $p$ modulo $8$.

If $p \equiv 1 \pmod 8$, $\legendre{2}{p} =\legendre{2}{1} = 1$.

If $p \equiv -1 \pmod 8$, $\legendre{2}{p} =\legendre{2}{-1} = 1$.

If $p \equiv \pm 3 \pmod 8$, $\legendre{2}{p} =\legendre{2}{\pm 3} = -1$.

\bigskip

Generalization: let $a>0$ and $p$ be an odd positive integer such that $p \wedge a =1$ (not necessarily prime).

$$\legendre{a}{p} = \legendre{4a p}{p} = \legendre{4a-p}{p} = (-1)^{\frac{4a - p -1}{2} \frac{p-1}{2}} \legendre{p}{4a-p}.$$
$(4a-p-1)(p-1)=  4a(p-1)  + 1 - p^2 \equiv 0 \pmod 8$, so 
$$\legendre{a}{p} =  \legendre{p}{4a-p}.$$
As $\legendre{p}{-1} = 1$,
$$  \legendre{p}{4a-p} =   \legendre{p}{p-4a}.$$
Since $p \equiv 4a \pmod {p-4a}$,  and $4$ is a square,
$$\legendre{p}{p-4a} \equiv \legendre{4a}{p-4a} =  \legendre{a}{p-4a}.$$

We have proved
$$\legendre{a}{p} = \legendre{4a-p}{p} =  \legendre{p}{p-4a} = \legendre{4a}{p-4a}  =  \legendre{a}{p-4a}.$$

By induction, for all $k\geq 0$, $\legendre{a}{p} = \legendre{a}{p-4ka}$, so $\legendre{a}{p}$ depends only of the class of $p$ modulo $4a$.

\newpage

{ \Large \bf Chapter 6} 

\paragraph{Ex. 6.1}

{\it Show that $\sqrt{2} + \sqrt{3}$ is an algebraic integer.
}

\begin{proof}
Let $x = \sqrt{2}+\sqrt{3}$. Then $x^2 = 5 + 2\sqrt{6}$.

$(x^2-5)^2 = (2 \sqrt{6})^2 = 24$, so $x^4 - 10 x^2 + 1 = 0$ :  $x$ is an algebraic integer.
\end{proof}

\paragraph{Ex. 6.2}

{\it Let $\alpha$ be an algebraic number. Show that there's an integer $n$ such that $n\alpha$ is an algebraic integer.
}

($0$ is a valid answer to this sentence ! More seriously, we search a {\it positive} integer $n$.)

\begin{proof} 

Let  $\alpha$ an algebraic number.  By definition, there exist $a_0,a_1,\cdots,a_n \in \Z, a_n \neq 0,$ such that
$$a_n \alpha^n+ a_{n-1} \alpha^{n-1} + \cdots + a_k \alpha^k+\cdots +a_0 = 0.$$
(Up to multiply this equation by $-1$, we can suppose that $a_n >0$). 

Multiplying by $a_n^{n-1}$, we obtain
$$a_n^n \alpha^n+ a_n^{n-1}a_{n-1} \alpha^{n-1} + \cdots + a_n^{n-1} a_k \alpha^k+\cdots + a_n^{n-1} a_0 = 0.$$
So
$$(a_n \alpha)^n+ a_{n-1} (a_n\alpha)^{n-1} + \cdots + a_n^{n-k-1}a_k (a_n \alpha)^k+\cdots + a_n^{n-1} a_0 = 0.$$

Soit $p(x) = x^n +\sum\limits_{k=0}^{n-1} a_n^{n-k-1}a_k x^k$. Then $p(x) \in \mathbb{Z}[x]$, $p(x)$ is monic, and $p(a_n \alpha) = 0$. So $a_n \alpha$ is an algebraic integer, with $m = a_n \in \mathbb{N}^*$.

Conclusion : if  $\alpha$ is an algebraic number, there exists an integer $m >0$ such that $m\alpha$ is an algebraic integer.
\end{proof}

\paragraph{Ex. 6.3}

{\it If $\alpha$ and $\beta$ are algebraic integers, prove that any solution to $f(x) = x^2 + \alpha x + \beta = 0$ is an algebraic integer. Generalize this result.
}

\begin{proof}

Let $\gamma$  be a root of  $x^2 + \alpha x + \beta$, where $\alpha, \beta$ verify :
$$\alpha^n + r_1 \alpha^{n-1}+ \cdots + r_n = 0,\quad r_i \in \mathbb{Z},$$
$$\beta^m + s_1 \beta^{m-1}+ \cdots + s_m= 0,\quad  s_j \in \mathbb{Z}.$$

Let $V$ the set of linear combinations with integer coefficients of 
$$\alpha^i \beta^j \gamma^k, 0\leq i <n,0 \leq j <m,0 \leq k <2.$$

Then $V$ if a finitely generated $\Z$-module. 

Moreover, for all  $\delta \in V, \gamma \delta \in V$. Indeed, every $\delta \in V$ is a linear combination with coefficients in $\Z$ of $\alpha^i \beta^j, \alpha^i \beta^j \gamma$, and
 \begin{align*}
 \gamma (\alpha^i \beta^j) &= \alpha^i \beta^j \gamma \in V\\
 \gamma(\alpha^i \beta^j \gamma) &= \alpha^i \beta ^j \gamma^2 = \alpha^i \beta^j (-\alpha \gamma - \beta) = - \alpha ^{i+1} \beta^j \gamma - \alpha^i \beta^{j+1} \in V.
 \end{align*}
 (if $i+1 = n$, we replace $\alpha^{i+1} = \alpha^n$ by $ -\sum\limits_{k=1}^{n-1} r_k \alpha^{n-k}$, and a similar replacement if if $j+1 = m$.)
 
 As for each $x\in V$, where $V$ if a finitely generated $\Z$-module, $x \gamma \in V$, so  $\gamma$ is an algebraic integer (Proposition 6.1.4).

More generally,  if  $\gamma^n + \alpha_1 \gamma^{n-1}+ \cdots + \alpha_n = 0$, where the $\alpha_i$ are algebraic integers, then  $x$ is an algebraic integer.
\end{proof}

\paragraph{Ex. 6.4}

{\it A polynomial $f(x) \in \Z[x]$ is said to be primitive if the greatest common divisor of its coefficients is 1. Prove that the product of primitive polynomials is also primitive.}

\bigskip

{\bf Solution 1}
\begin{proof}
Let $p(x) =\sum_{i=0}^n a_i x^i, q(x) = \sum_{j=0}^m b_j x^j$ two primitive polynomials, and $p$ a prime number. There exist a coefficient of $p(x)$ (and of $q(x)$) not divisible by $p$.
Let 
\begin{align*}
i_0 &= \min\{i \in [0,n]\ \  \vert \ a_i \not \equiv 0 \ [p]\}\\
j_0 &= \min\{j \in [0,m]\ \vert\  b_j \not \equiv 0 \ [p]\}\\
\end{align*}
Let $p(x) q(x) = \sum_{k=0}^{n+m} c_k x^k$. Then $c_k = \sum\limits_{i+j = k} a_i b_{j}, \ k=0,\ldots n+m$.
Then $$c_{i_0+j_0} = \sum_{i+j = i_0+j_0} a_i b_j.$$

$\bullet$ If $i<i_0$, then $a_i \equiv 0 \pmod p$.

$\bullet$ If $i>i_0$, then $j<j_0$ and $b_j \equiv 0 \pmod p$.

In the two cases $a_i b_j \equiv 0 \pmod p$, so $c_{i_0+j_0} \equiv a_{i_0} b_{j_0} \pmod p$, so $c_{j_0} \not \equiv 0 \pmod p$. As it's true for all primes $p$, the polynomial $p(x)q(x)$ is primitive.
\end{proof}

\bigskip

{\bf Solution 2}
\begin{proof}
Let
$$
\varphi : 
\left\{
\begin{array}{ccc}
  \Z[x]&   \to & \F_p[x]  \\
  p(x)= a_0 +\cdots+a_n x^n& \mapsto  & \overline{p}(x) =  \overline{a_0}+\cdots+\overline{a_n}x^n,
\end{array}
\right.
$$
where $\overline{a_i}$ is the class of $a_i$ in $\F_p$.  $\varphi$ is a ring homomorphism.

As $\F_p[x]$ is an integrity domain, if $p(x), q(x)$ are both primitive,
$$\overline{p(x)} \ne 0, \overline{q(x)} \ne 0 \Rightarrow \overline{p(x)q(x)} =\overline{p(x)}\,   \overline{q(x)}  \ne 0.$$
As $\overline{p(x)q(x)} \ne 0$ in all fields $\F_p$, $p(x)q(x)$ is a primitive polynomial.
\end{proof}

\paragraph{Ex. 6.5}
{\it Let $\alpha$ be an algebraic integer and $f(x) \in \Q[x]$ be the monic polynomial of least degree such that $f(\alpha) = 0$. Use Exercise 6.4 to show that $f(x) \in \Z[x]$.
}

\begin{proof}
As $\alpha$ is an algebraic integer, there exists a monic polynomial $h(x) \in \Z[x]$ such that $h(\alpha) = 0$. As $f(x) \in \Q[x]$ is the minimal polynomial  of $\alpha$, and $h(\alpha) = 0$, $f(x)$ divides $h(x)$ in $\Q[x]$.

 (Quick reminder :  $h(x) = q(x) f(x) + r(x),\  q(x),r(x) \in \Q[x],  \deg(r(x)) < \deg(f(x))$ or $r(x) = 0$. As $r(\alpha) = 0$ and $f(x) \in \Q[x]$ is  the monic polynomial of least degree such that $f(\alpha) = 0$, $r =0$ so $f(x) \mid h(x)$).
 
 So there exists $g(x) \in \Q[x]$ such that $h(x) = f(x) g(x)$. As $h(x), f(x)$ are both monic, $g(x)$ is also monic. 
 
 Let $d \in \Z, d\ne 0$ such that $df(x) =\sum_{i=0}^m a_i x^i \in \Z[x]$, and $c = a_1\wedge a_2\wedge \cdots \wedge a_m$, $a_i = c b_i$, with $b_1\wedge b_2\wedge \cdots \wedge b_m = 1$, so
 $f(x) = \frac{c}{d} f_1(x) $, where $f_1$ is primitive. Similarly $g(x) =\frac{s}{t} g_1(x)$, $s ,t \in \Z$,  $g_1(x)$ primitive.
 
 So $h(x) = \frac{cs}{dt} f_1(x) f_2(x) = \frac{u}{v} f_1(x) f_2(x) $, where $u\wedge v = 1, v>0$.
The polynomial $f_1(x)f_2(x) = \sum_{k=0}^r c_k x^k$ is primitive (Ex. 6.4). As $vh(x)= u f_1(x)f_2(x)$, $v \mid uc_k$ , and $u\wedge v = 1$, thus $v \mid c_k, k=0,1,\ldots,r$. As $c_1 \wedge \cdots c_k = 1$, $v \mid 1$, where $v>0$, so $v =  1$. $h(x) = u f_1(x) f_2(x)$ is monic, thus $u=\pm 1$, and $\pm f_1,\pm f_2$ are monic. From $f(x) = \frac{c}{d} f_1(x)$ we deduce $\frac{c}{d} = \pm 1$ and $f(x) = \pm f_1(x) \in \Z[x]$.

Conclusion : if $f(x)$ is the minimal polynomial of an algebraic integer $\alpha$, $f \in \Z[x]$.
\end{proof}

\paragraph{Ex. 6.6}

{\it Let $x^2 + mx + n \in \Z[x]$ be irreducible, and $\alpha$ be a root. Show that $\Q[\alpha] = \{r +s\alpha: r, s \in \Q\}$ is a ring (in fact, it is a field). Let $m^2 - 4n = D_0^2 D$, where $D$ is square-free. Show that $\Q[\alpha] = \Q[\sqrt{D}]$.
}

\begin{proof}
By definition, for all $z \in \C, z \in \Q[\alpha] \iff \exists P \in \Q[x], z = P(\alpha)$.

The Euclidean division gives $P = Q_1 (x^2+mx+n) + R, \ Q_1,R  \in \Q[x], \deg(R) < 2$, so $R = rx+s,\ r,s \in \Q$. Therefore $z = Q_1(\alpha) (\alpha^2+m\alpha+n) + r\alpha + s = r\alpha + s$ :
$$\Q[\alpha] = \{z \in \C\ \vert \ \exists r \in \Q, \exists s \in \Q, \ z = r+s \alpha\}.$$

$\bullet$ $\Q[\alpha] \subset \C$, where $(\C,+,\times)$ is a field. $1 \in \Q[\alpha]$ ($1 = P_0(\alpha)$, where $P_0$ is the constant polynomial $1$).

$\bullet$ Let $\beta, \gamma \in \Q[\alpha] : \beta = P(\alpha), \gamma = Q(\alpha)$, where $P,Q$ are in $\Q[x]$.
Then $\alpha - \beta =  P(\alpha) -  Q(\alpha) = R(\alpha)$, where $R = P-Q \in \Q[x]$, and $\alpha \beta =  P(\alpha) Q(\alpha) = S(\alpha)$, where $S = PQ \in \Q[x]$. Thus $\alpha - \beta \in \Q[\alpha], \alpha \beta \in \Q[\alpha]$. So $\Q[\alpha]$ is a subring of $(\C,+,\times)$.

$\bullet$ Let $\beta = P(\alpha) \in \Q[\alpha], P \in \Q[x]$ and $\beta \neq 0$.
As $\beta \ne 0$, $Q = x^2+mx+n \nmid P$. 

Let $D \in \Q[x]$  such that $D \mid P,D \mid Q$. As $Q$ is irreducible by hypothesis, $D = \lambda$ or $D = \lambda Q, \lambda \in \C^*$ ($D$ is an associate of $1$ or $Q$). If $D = \lambda Q$, then $Q \mid D$, and $D \mid P$, so $Q \mid P$. Since $Q(\alpha) = 0$,  this implies $\beta = P(\alpha) = 0$, in contradiction with the definition of $\beta$. So $D = \lambda \mid 1$. Therefore $P\wedge Q = 1$. 

From B\'{e}zout's theorem, there exist polynomials $U,V \in \Q[x]$ such that $UP+VQ = 1$. As $\Q(\alpha) = 0$, $U(\alpha) P(\alpha) = 1$ and $\gamma = U(\alpha) \in \Q[\alpha]$ is such that $\gamma \beta$ = 1. Therefore $\Q[\alpha]$ is a subfield of $(\C,+,\times)$ (and $\Q(\alpha) = \Q[\alpha]$).

As $x^2+mx+n$ is irreducible, $\Delta = m^2-4n \ne 0$ (if not, $x^2+mx +n = (x+m/2)^2 -(m^2 -4n)/4 = (x +m/2)^2$ is not irreducible). So $\Delta \in \Z \setminus\{ 0\}$ can be written $\Delta = m^2 - 4n = D_0^2D$, where $D$ is square-free (positive or negative), $D \neq 0, D_0 \neq 0$.

$\alpha = -\frac{m}{2} + \varepsilon\frac{\sqrt{\Delta}}{2},\ \varepsilon = \pm 1$, 
so $\alpha = -\frac{m}{2} + \varepsilon D_0 \frac{\sqrt{D}}{2}$, thus  $\alpha \in \Q[\sqrt{D}]$ and $\Q[\alpha] \subset \Q[\sqrt{D}]$.

 As $D_0 \neq 0$, $\sqrt{D} = \varepsilon \frac{2 \alpha + m}{D_0} \in \Q[\alpha]$, 
 so $\Q[\sqrt{D}] \subset \Q[\alpha)]$ :
$$\Q[\alpha] = \Q[\sqrt{D}].$$ 
\end{proof}

\paragraph{Ex. 6.7}

{\it (continuation) If $D \equiv 2, 3  \pmod 4$, show that all the algebraic integers in $\Q[\sqrt{D}]$ have the form $a + b \sqrt{D}$, where $a, b \in \Z$. If $D \equiv 1  \pmod 4$, show that all the algebraic integers in $\Q[\sqrt{D}]$ have the form $a + b((-1 + \sqrt{D})/2)$, where $a, b \in \Z$.
}

\begin{proof}
(We write $\overline{\Z}$ the ring of algebraic integers in $\C$, and ${\cal O}_K$ (or $\Z_K$) the ring of algebraic integers in the field $K$.)

If $D=1$, $\Q[\sqrt{D}] = \Q$. If $D \neq 1$, as $D$ is square-free, $D$ is not a square, so $\sqrt{D}$ is irrational.

Let $\gamma = r + s \sqrt{D} \in \Q[\sqrt{D}]\ (r,s \in \Q)$ an algebraic integer of $\Q[\sqrt{D}]$ ($D\in \Z, D$ square-free).
$(\gamma - r)^2 = s^2 D$, so  $\gamma^2 - 2r\gamma +r^2 - Ds^2 = 0$. $\gamma$ is a root of 
$$p(x) = x^2-2rx+r^2-Ds^2.$$

If $s = 0$, then the minimal polynomial of $\gamma$ is $x-r$.  As $r = \gamma $ is an algebraic integer and $r\in \Q$, then $r\in \Z$. In this case $r\in \Z$ and $s=0$.

If $s\neq 0$, $\gamma \not \in \Q$, so no polynom of degree $d\leq 1$ has the root $\gamma$. Thus the minimal polynomial of $\gamma$ is $p(x)$. From Exercise 6.5, $p(x) \in \Z[x]$, so (in the two cases $s=0,s\neq 0$)
$$2r \in \Z, r^2-Ds^2 \in \Z.$$
Conversely, if $2r \in \Z, r^2-Ds^2 \in \Z$, then $p(x)\in \Z[x]$ and $p(\gamma) = 0$, thus $\gamma$ is an algebraic integer.

If  $r,s \in \Q$, $D\neq 1$ square-free,
$$r+s\sqrt{D} \in \overline{\Z}  \iff 2r \in \Z,\  r^2-Ds^2 \in \Z.$$
Let $\gamma =  r + s \sqrt{D} \in \overline{\Z}$.
We can write $$r = \frac{a}{d}, s = \frac{b}{d}, \qquad a,b,d \in \Z, d\geq 1, d\wedge a \wedge b = 1.$$
Then
$$n = \frac{2a}{d} \in \Z, \quad m = \frac{a^2-Db^2}{d^2} \in \Z.$$
As $D$ is square-free, $D\not \equiv 0 \pmod 4$.
\begin{enumerate}
\item[$\bullet$] Case 1: $D \equiv 2,3 \pmod 4$.

$n^2-4m = \frac{4Db^2}{d^2}$, so $d \mid 2a, d^2 \mid 4Db^2$.

If $2\mid d$, $4 \mid a^2-Db^2$, $a^2 \equiv Db^2 \pmod 4$.
As $d\wedge a \wedge b = 1$, and $2 \mid d$, $a$ or $b$ is odd, and $a^2 \equiv Db^2 \pmod 4, D \not \equiv 0 \pmod 4$, implies that $a$ and $b$ are both odd. Then $a^2 \equiv b^2 \equiv 1 \pmod 4$, so $D \equiv 1 \pmod 4$ : this is in contradiction with the hypothesis $D \equiv 2,3 \pmod 4$. So $d$ is an odd number.

Consequently, $d\mid a, d^2 \mid Db^2$. If $p\in \N$ is a prime factor of $d$, $p \mid d, p \mid a$, and $d \wedge a \wedge b = 1$, thus $p \nmid b$, and since $p^2 \mid D b^2$, $p^2 \mid D$, in contradiction with $D$ square-free. So $d\geq 1$ has no prime factor : $d = 1$ and $r = a,s = b \in \Z$. Conversely, any $\gamma = a+b\sqrt{D}, a,b \in \Z$ is an algebraic integer, so 
$${\cal O}_{\Q[{\sqrt{D}}]} = \overline{\Z} \cap \Q[{\sqrt{D}}] = \{a + b \sqrt{D}\ \vert \ a,b \in \Z\}.$$

\item[$\bullet$] Case 2: $D \equiv 1 \pmod 4$.

Then $r = \frac{n}{2}, n \in \Z$. Write $s = \frac{u}{v}, u \wedge v = 1, v \geq 1$.

$m = r^2 - D s^2 = \frac{n^2}{4} - D \frac{u^2}{v^2} \in \Z$, $4 D \frac{u^2}{v^2} = n^2 - 4 m \in \Z$, so $v^2 \mid 4 D u^2$. Since $u\wedge v = 1, u^2 \wedge v^2 = 1$, so  $v^2 \mid 4 D$. As $D$ is square-free, $v$ has no odd prime factor, so $v = 2^k$. Since $D$ is odd, $k\leq1$ and $v = 1$ or $v = 2$. So $r,s$ are both half-integers: $r = n/2, s = n'/2,\ n,n' \in \Z$.

$4 m = n^2 - D n'^2$, thus $n^2 \equiv n'^2 \pmod 4$, so $n,n'$ have the same parity. Let $a = \frac{n+n'}{2} \in \Z, b = n' \in \Z$. Then $n = 2a -b, n' = b$ and  $\gamma = \frac{n}{2} + \frac{n'}{2} \sqrt{D} =  a - \frac{b}{2} + \frac{b}{2} \sqrt{D} = a + b\left( \frac{-1+ \sqrt{D}}{2} \right)$.

Conversely, $\frac{-1+ \sqrt{D}}{2}$ is a root of $x^2 + x +\frac{1-D^2}{4} \in \Z[x]$, so every $a + b\left( \frac{-1+ \sqrt{D}}{2} \right)$ is an algebraic integer.
$${\cal O}_{\Q[{\sqrt{D}}]} = \overline{\Z} \cap \Q[{\sqrt{D}}] = \{a + b\left( \frac{-1+ \sqrt{D}}{2} \right)\ \vert \ a,b \in \Z\}.$$
\end{enumerate}
\end{proof}

\paragraph{Ex. 6.8}

{\it Let $\omega = e^{2 \pi i/3}$, $\omega$ satisfies $x^3 - 1 = 0$. Show that $(2 \omega + 1)^2 = -3$, and use this to determine $(-3/p)$ by the method of section $2$.
}

\begin{proof}
As $\omega^2+\omega+1 = 0$,$(2\omega+1)^2 = 4\omega^2+4\omega+1 = -4+1 = -3$. Let $\alpha = 2\omega+1$, so that $\alpha^2 = -3$
\begin{align*}
\legendre{-3}{p} &\equiv (-3)^{(p-1)/2} \pmod p\\
&\equiv \alpha^{p-1} \pmod p
\end{align*}
$$\alpha^p = \legendre{-3}{p} \alpha.$$
From Prop. 6.1.6,
\begin{align*}
\alpha^p &= (2\omega+1)^p\\
&\equiv 2^p \omega^p + 1 \pmod p\\
&\equiv 2 \omega^p + 1\pmod p
\end{align*}
\begin{enumerate}
\item[$\bullet$] If $p \equiv 0 \pmod 3$, $\legendre{-3}{p} = 0$.
\item[$\bullet$] If $p \equiv 1 \pmod 3$, $\omega^p  = \omega$, so $\alpha^p \equiv \alpha \pmod p$.

$\legendre{-3}{p} \alpha \equiv \alpha \pmod p$, thus $\legendre{-3}{p} \alpha^2 \equiv \alpha^2 \pmod p$, $\legendre{-3}{p} 3 \equiv 3 \pmod p$. As $p \wedge 3 = 1$, $\legendre{-3}{p}  \equiv 1 \pmod p$. Since $\legendre{-3}{p} = \pm 1$,  $\legendre{-3}{p}  = 1$.

\item[$\bullet$] If $p \equiv -1 \pmod 3$, $\omega^p = \omega^{-1} = \omega^2$, and
\begin{align*}
\alpha^p &\equiv 2 \omega^p + 1 \pmod p\\
&\equiv 2\omega^2 + 1 = 2(-1-\omega)+1 = -2 \omega - 1 = -\alpha\pmod p.\\
\end{align*}
$\legendre{-3}{p} \alpha \equiv -\alpha \pmod p$, thus $\legendre{-3}{p} \alpha^2 \equiv -\alpha^2 \pmod p$, $\legendre{-3}{p} 3 \equiv -3 \pmod p$. As $p \wedge 3 = 1$, $\legendre{-3}{p}  \equiv -1 \pmod p$. Since $\legendre{-3}{p} = \pm 1$,  $\legendre{-3}{p}  = -1$.
\end{enumerate}
Conclusion : 
\begin{align*}
p \equiv 0 [3] &\iff \legendre{-3}{p} = 0,\\
p \equiv 1 [3] &\iff \legendre{-3}{p} = 1,\\
p \equiv -1 [3] &\iff \legendre{-3}{p} = -1.\\
\end{align*}
In other words, $ \legendre{-3}{p} =  \legendre{p}{3}$.

Note : $\alpha = 2 \omega + 1 = \omega - \omega^2 = g$ is the quadratic Gauss sum for $p=3$.
\end{proof}

\paragraph{Ex. 6.9}

{\it Verify Proposition 6.3.2 explicitly for $p = 3, 5$, i.e., write out the Gauss sum longhand and square.
}

\begin{proof}
\begin{enumerate}
\item[$\bullet$] p=3. Let $\omega = e^{2i\pi/3}$.
Let $g = \sum_{t=0}^2 (t/3)\omega^t$ the quadratic Gauss sum. Then $g =\omega - \omega^2$.

As $1+\omega+\omega^2 = 0$,
$g^2 = (\omega- \omega^2)^2 = \omega^2 - 2 \omega^3 + \omega^4 = \omega^2 - 2 + \omega  =-3$ :

$$g^2 = -3.$$

\item[$\bullet$] p=5. Let $\zeta= e^{2i\pi/5}$.

$g = \sum_{t=0}^4 (t/3)\zeta^t = \zeta- \zeta^2-\zeta^3+\zeta^4.$ 

Then $g = \alpha - \beta$, where $\alpha = \zeta + \zeta^4, \beta = \zeta^2+\zeta^3$.

$\alpha + \beta = \zeta + \zeta^4+\zeta^2 + \zeta^3 = -1$.

$\alpha \beta= \zeta^3+ \zeta^4+\zeta^6+\zeta^7 = \zeta^3+ \zeta^4+\zeta+\zeta^2 = -1$

So $\alpha, \beta$ are the two roots of $x^2+x-1$.
\begin{align*}
g^2 &= (\alpha - \beta)^2\\
&=\alpha^2+\beta^2 - 2 \alpha \beta\\
&=(\alpha+ \beta)^2 - 4 \alpha \beta\\
&= (-1)^2-4(-1)\\
&= 5.
\end{align*}

Note: here we know explicitely $g$ :

if $p = 3$, $g = \omega - \omega^2 = i \sqrt{3}$.

If $p=5$, $g = \alpha - \beta = (-1+\sqrt{5})/2 - (-1 - \sqrt{5})/2 = \sqrt{5}$.
\end{enumerate}
\end{proof}

\paragraph{Ex. 6.10}

{\it  What is $\sum_{a=1}^{p-1} g_a$?
}

\begin{proof}
From Prop. 6.3.1 and Lemma 2,
$$\sum_{a=1}^{p-1} g_a = g_1 \sum_{a=1}^{p-1} \legendre{a}{p} = 0.$$
\end{proof}

\paragraph{Ex. 6.11}

{\it By evaluating $\sum_t (1+(t/p)) \zeta^t$ in two ways, prove that $g = \sum_t \zeta^{t^2}$.
}

\begin{proof}
For $ a \in \F_p$, Write $N[x^2 = a]$ the number of solutions of the equation $x^2 = a$ in $\F_p$.
We know from Ex. 5.2 that $N[x^2 = a] = 1 + (a/p)$. Therefore
\begin{align*}
\sum_{t=0}^{p-1} \zeta^{t^2} &= \sum_{\overline{t} \in \F_p} \zeta^{t^2} \\
 & = \sum_{\overline{a} \in \F_p} N[x^2 = a] \zeta^a\\
&=\sum_{\overline{t} \in \F_p} \left(1 + \legendre{t}{p} \right) \zeta^t\\
&=\sum_{\overline{t} \in \F_p} \zeta ^t + \sum_{\overline{t} \in \F_p}  \legendre{t}{p} \zeta^t\\
 &=\sum_{t = 0} ^{p-1}  \legendre{t}{p} \zeta^t\\
 &= g
\end{align*}
\end{proof}

\paragraph{Ex. 6.12}

{\it Write $\psi_a(t) = \zeta^{at}$. Show that
\begin{enumerate}
\item[(a)] $\overline{\psi_a(t)} = \psi_a(-t) = \psi_{-a}(t)$
\item[(b)] $(1/p)\sum_a \psi_a(t-s) = \delta(t, s)$
\end{enumerate}
}

\begin{proof}
\begin{enumerate}
\item[(a)]  Let $a\in \Z$. As $\overline{\zeta} = \zeta^{-1}$, 
\begin{align*}
\overline{\psi_a(t)} &=\overline{\zeta^{at}}= \zeta^{-at}\\
& = \zeta^{a(-t)} = \zeta^{(-a)t}\\
& = \psi_a(-t) = \psi_{-a}(t)
\end{align*}
$\overline{\psi_a(t)} = \psi_a(-t) = \psi_{-a}(t)$
\item[(b)] 
From Corollary of Lemma 1 :
$$\frac{1}{p} \sum_{a=0}^{p-1} \psi_a(t-s) = \frac{1}{p} \sum_{a=0}^{p-1} \zeta^{a(t-s)} = \delta(t,s)$$
$$\frac{1}{p}\sum_a \psi_a(t-s) = \delta(t, s).$$
\end{enumerate}
\end{proof}

\paragraph{Ex. 6.13}

{\it Let $f$ be a function from $\Z$ to the complex numbers. Suppose that $p$ is a prime and that $f(n+p) = f(n)$ for all $n \in \Z$. Let $\hat{f}(a) = p^{-1} \sum_t f(t) \psi_{-a}(t)$. Prove that $f(t) = \sum_a\hat{f}(a)\psi_a(t)$. This result is directly analogous to a result in the theory of Fourier series.
}

\begin{proof}
Let $\hat{f}(a) = p^{-1} \sum_t f(t) \psi_{-a}(t)$. Then
\begin{align*}
\sum_{a=0}^{p-1} \hat{f}(a) \psi_a(t) &= \sum_{a=0}^{p-1} p^{-1} \sum_{s=0}^{p-1} f(s) \psi_{-a}(s) \psi_{a}(t)\\
&=p^{-1} \sum_{s=0}^{p-1}f(s)  \sum_{a=0}^{p-1}  \psi_{-a}(s) \psi_{a}(t)\\
&=p^{-1} \sum_{s=0}^{p-1}f(s)  \sum_{a=0}^{p-1}  \psi_{a}(t-s) \\
&= \sum_{s=0}^{p-1} f(s) \delta(s,t)\\
&=f(t)
\end{align*}
\end{proof}

\paragraph{Ex. 6.14}

{\it In Ex. 13 take $f$ to be the Legendre symbol and show that $\hat{f}(a) = p^{-1} g_{-a}$.
}

\begin{proof}
Here $f(a) = \legendre{a}{p}$. Then
$\hat{f}(a) = p^{-1} \sum_{t=0}^{p-1} \legendre{t}{p} \zeta^{-at} = p^{-1} g_{-a}$.
\end{proof}

\paragraph{Ex. 6.15}

{\it Show that
$$ \left|\sum_{t = n}^m \legendre{t}{p}\right| < \sqrt{p}\log p.$$
The inequality holds for the sum over any range.
}


{\bf Lemma.} If $0\leq x \leq \frac{\pi}{2}, \sin x \geq \frac{2}{\pi} x$.
\begin{proof}
As $-\sin$ is a convex function on $[0,\pi/2]$, the graph of $\sin$ is above any chord, and the chord between the points $(0,0)$ and $(\pi/2,1)$ has equation $y = (2/\pi) x$, we conclude that
 $\sin x \geq \frac{2}{\pi} x$ for $0\leq x \leq \pi/2$. 
\end{proof}
\begin{proof}
Let $S = \sum\limits_{t = n}^m \legendre{t}{p} g$ with $n\leq m$. Then $\vert S \vert = \sqrt{p} \left|\sum\limits_{t = n}^m \legendre{t}{p}\right|$. As $(t/p)g = g_t$,
\begin{align*}
S&= \sum _{t=m}^n g_t\\
&=\sum _{t=m}^n \sum_{s=0}^{p-1}\legendre{s}{p} \zeta^{ts}\\
&=\sum_{s=0}^{p-1} \legendre{s}{p} \zeta^{ms} \sum _{t=m}^n \zeta^{(t-m)s}\\
&=\sum_{s=0}^{p-1} \legendre{s}{p} \zeta^{ms} \sum _{u=0}^{n-m} \zeta^{us} \qquad( u=t-m)\\
&=\sum_{s=1}^{p-1} \legendre{s}{p} \zeta^{ms} \frac{\zeta^{(n-m+1)s}-1}{\zeta^s-1}\\
\end{align*}
(since for $s=0$, the sum $\sum _{u=0}^{n-m} \zeta^{us} = n-m+1$ and $\legendre{s}{p} = 0$). So
\begin{align*}
S &= \sum_{s=1}^{p-1} \legendre{s}{p} \frac{\zeta^{(n+1)s}-\zeta^{ms}}{\zeta^s-1}\\
&=\sum_{s=1}^{p-1} \legendre{s}{p} \frac{\zeta^{\frac{n+m+1}{2} s}}{\zeta^{\frac{s}{2}}} \  \frac{\zeta^{\frac{n-m+1}{2} s}-\zeta^{\frac{-n+m-1}{2} s}}{\zeta^{\frac{s}{2}}-\zeta^{\frac{-s}{2}}}\\
&= \sum_{s=1}^{p-1} \legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right) }
\end{align*}
As $\sin(x) \geq \frac{2}{\pi} x$ for $x \in [0,\frac{\pi}{2}]$, for all $s$, $1\leq s <\frac{p}{2}$, $0 \leq \frac{s \pi}{p} \leq \frac{\pi}{2} $, so
$$\left| \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right)} \right |  \leq \frac{1}{\frac{2}{\pi} \left(s\frac{\pi}{p} \right)} = \frac{p}{2s}\qquad (s = 1,2,\ldots,(p-1)/2).$$
Since $\legendre{s}{p} \zeta^{ts}$ depends only of the class of $s$, we can replace in the preceding calculation the values $s = 1,2,\ldots,p-1$ by $s=-(p-1)/2,\ldots, -1,1,\ldots,(p-1)/2$, so
$$S = \sum_{s=1}^{(p-1)/2}\legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right) }
+\sum_{s=-(p-1)/2}^{-1} \legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right) }.$$
As $\sin$ is an odd function,
$$S = \sum_{s=1}^{(p-1)/2}\legendre{s}{p}\zeta^{\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right) }
+\sum_{s=1}^{(p-1)/2} \legendre{-s}{p}\zeta^{-\frac{n+m}{2} s} \ \frac{\sin \left((n-m+1)s \frac{\pi}{p}\right)} { \sin \left(s \frac{\pi}{p}\right) }.$$
Thus 
$$\vert S \vert \leq 2 \sum_{s=1}^{(p-1)/2}\frac{p}{2s} = p\sum_{s=1}^{(p-1)/2} \frac{1}{s}.$$
As $S = \sum\limits_{t = n}^m \legendre{t}{p} g$ and $|g| = \sqrt{p}$,
$$ \left|\sum_{t = n}^m \legendre{t}{p}\right| \leq \sqrt{p} \sum_{s=1}^{(p-1)/2} \frac{1}{s}.$$
It remains to do a sufficient estimation of the harmonic sum. 
We prove by induction that for all $n \geq 1$,
$$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \log(2n+1).$$
As $1 \leq \log(3)$, this proposition is true for $n=1$. Suppose that is it true for $n-1$ :
$$1+\frac{1}{2}+\cdots+\frac{1}{n-1} \leq \log(2n-1).$$
Then $$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \frac{1}{n} + \log(2n-1).$$
If we prove that $\frac{1}{n} + \log(2n-1) \leq \log(2n+1)$, the induction is done.

Let $u(x) = \log(2x+1) - \log(2x-1) - \frac{1}{x}, x > \frac{1}{2}$.
\begin{align*}
u'(x) &= \frac{2}{2x+1} - \frac{2}{2x-1} +\frac{1}{x^2}\\
&=\frac{-4}{4x^2-1} + \frac{1}{x^2}\\
&= \frac{-1}{(4x^2-1)x^2} <0
\end{align*}
As $u(x) = \log\left(\frac{2x+1}{2x-1}\right)  - \frac{1}{x}$, $ \lim\limits_{x\to +\infty} u(x) =0$. Moreover $u$ is a decreasing function, so for all $x>1/2, u(x)>0$, and for all $n\in \N, n\geq 1$,
$$\frac{1}{n} + \log(2n-1) \leq \log(2n+1).$$
We have proved by induction that for all $n\geq 1$,
$$1+\frac{1}{2}+\cdots+\frac{1}{n} \leq \log(2n+1).$$
If $n = (p-1)/2$, where $p$ is an odd prime ($p\geq 3$),
$$\sum_{s=1}^{(p-1)/2} \frac{1}{s} \leq \log p.$$
Conclusion: $$ \left|\sum_{t = n}^m \legendre{t}{p}\right| < \sqrt{p}\log p.$$
\end{proof}

\paragraph{Ex. 6.16}

{\it Let $\alpha$ be an algebraic number with minimal polynomial
$f(x)$. Show that $f(x)$ does not have repeated roots in $\C$.
}

\begin{proof}
Let $\gamma$ a repeated root of $f(x)$. Then $f(\gamma) = f'(\gamma) = 0$, so $x -\gamma$ is a common factor of $f$ and $f'$. Thus  $f \wedge f' \neq 1$ ($ \deg(f\wedge f') \geq 1)$.
Since $f \wedge f' \mid f$ and $f$ is irreducible (with $f$ , $f\wedge f'$ monic), we conclude $f\wedge f' = f$, so $f \mid f'$. In $\C$, this is impossible since $\deg(f) \geq 1$, thus $f'\neq 0$, and $\deg(f') < \deg(f)$. $f(x)$ does not have repeated roots in $\C$.
\end{proof}

\paragraph{Ex. 6.17}

{\it Show that the minimal polynomial for $\sqrt[3]{2}$ is $x^3 -2$.
}

\begin{proof}
Let $f(x) = x^3-2$. Then $f(\sqrt[3]{2}) = 0$.
If $f(x)$ was not irreducible, then $f(x) = u(x) v(x)$, with $1\leq \deg(u) \leq \deg(v) \leq 2, \deg(u) + \deg(v) = \deg(f) = 3$, so $\deg(u) = 1,\deg(v) = 2$.

Then $f(x) = (ax+b)(cx^2+dx+e), \ a,b,c,d,e \in \Q$.
Let $w = -b/a$. Then $f(w) = w^3 - 2= 0$ and $w\in \Q$, so there exist $p,q\in \Z$, such that $w = p/q, p\wedge q = 1$.

Thus $p^3 = 2 q^3$, so $p^3$ is even, thefore $p$ is even : $p = 2 p', p' \in \Z$.

$8 p'^3 = 2 q^3$, $4p'^3 = q^3$, so $q^3$ is even, which implies that $q$ is even. Then $2 \mid p\wedge q = 1$ : this is a contradiction.

So $f(\sqrt[3]{2}) = 0$, and $f$ is monic, irreducible: $f$ is the minimal polynomial of $\sqrt[3]{2}$ on $\Q$.
\end{proof}

\paragraph{Ex. 6.18}

{\it Show that there exist algebraic numbers of arbitrarily high degree.
}

\begin{proof}
As $1+x+\cdots+x^{p-1}$ is irreducible on $\Q[x]$ (Prop. 6.4.1), the numbers $\zeta_p = e^{2i\pi/p}$, with $p$ prime number, are algebraic numbers of arbitrary large degree.
\end{proof}

\paragraph{Ex. 6.19}

{\it Find the conjugates of $\cos(2 \pi/5)$.
}

\begin{proof}
Let $\gamma = \cos(2 \pi/5)$, $\zeta= e^{2i\pi/5}$ and $\alpha = \zeta + \zeta^4, \beta= \zeta^2+\zeta^3$. 

Then $\gamma = \frac{\zeta + \zeta^{-1}}{2} = \frac{\zeta + \zeta^{4}}{2}  = \frac{\alpha}{2}$.

$\alpha + \beta = \zeta + \zeta^4+\zeta^2 + \zeta^3 = -1$.

$\alpha \beta= \zeta^3+ \zeta^4+\zeta^6+\zeta^7 = \zeta^3+ \zeta^4+\zeta+\zeta^2 = -1$

So $\alpha, \beta$ are the two roots of $x^2+x-1$ : 

$\alpha^2 + \alpha-1$ = 0, so $ 4(\alpha/2)^2 + 2 (\alpha/2) - 1=0$ : $\gamma = \alpha/2$ is a root of
$$f(x) = 4x^2+2x-1.$$
As $\Delta = 4 \times 5$, the two roots of $f$ are irrational. $\deg(f) = 2$ and $f$ has no root in $\Q$, so $f(x)$ is irreducible in $\Q[x]$. Therefore the minimal polynomial of $\gamma = \cos(2 \pi/5)$ is $f(x) = 4x^2+2x -1.$
The other root of $f$ is $\beta/2 = (\zeta^2+\zeta^3)/2 = \cos(4\pi/5)$.

Conclusion : the conjugates of $\gamma = \cos(2 \pi/5)$ are $\gamma = \cos(2 \pi/5)$ and $\cos(4 \pi/5)$.
\end{proof}

\paragraph{Ex. 6.20}

{\it Let $F$ be a subfield of $\C$ which is a finite-dimensional vector space over $\Q$ of degree $n$. Show that every element of $F$ is algebraic of degree at most $n$.
}

\begin{proof}
Let $\alpha \in F$, with $\dim_{\Q} F = n$.
Any subset of $n+1$ vectors in $F$ is linearly dependent, so $\{1,\alpha,\alpha^2,\cdots,\alpha^{n}\}$ is linearly dependent. 

Thus there exists $(a_0,\ldots,a_n) \in \Q^{n+1}, (a_0,\ldots,a_n) \ne (0,0,\ldots,0)$ such that $a_0+a_1\alpha +\cdots+a_n \alpha^n = 0$.

Let $f(x) = a_0+a_1x+\cdots+a_n x^n$. Then $f(x) \in \Q[x], f(x) \neq 0$ and $f(\alpha) = 0, \deg(f(x)) \leq n$. So  every element of $F$ is algebraic of degree at most $n$.
\end{proof}

\paragraph{Ex. 6.21}

{\it Let $f(x) = \sum_{n=0}^\infty a_n x^n/n!$ and $g(x) =\sum_{n=0}^\infty b_n x^n/n!$ be power series with $a_n$ and $b_n$integers. If $p$ is a prime such that $p\mid a_i$ for $i = 0, \ldots,
p-1$, show that each coefficient $c_t$ of the product $f(x)g(x) = \sum_{n=0}^\infty c_n x^n$ for $t = 0, \ldots, p-1$ may be written in the form $p(A/B)$, $p\not | B$.
}

\begin{proof}
Let $k \in \N, 0 \leq k \leq p-1$.
\begin{align*}
c_k &= \sum_{i+j=k} \frac{a_i}{i!}\frac{b_j}{j!}\\
&= \sum_{i=0}^k \frac{a_i}{i!}\frac{b_{k-i}}{(k-i)!}\\
&=\frac{1}{k!} \sum_{i=0}^k \binom{k}{i} a_i b_{k-i}
\end{align*}
As $k! \wedge p = 1$, and $\sum_{i=0}^k \binom{k}{i} a_i b_{k-i} \equiv 0 \pmod p$ for $k=0,1,\ldots,p-1$,

$c_k = p(A/B) , p \wedge B = 1$.
\end{proof}


\paragraph{Ex. 6.22}

{\it Show that the relation $\varepsilon \equiv 1 \pmod p$ in Proposition
6.4.4 can also be achieved by replacing $x$ by $1+t$ instead of $e^z$.
}

\begin{proof}(solution given by Mikomikon and A.Grounds (agrounds))

We know from the remark after Prop 6.4.3 that
$$g(\chi) = \varepsilon \prod_{k=1}^{(p-1)/2}(\zeta^{2k-1} - \zeta^{-(2k-1)}),$$
where $\varepsilon = \pm 1$.
Let $$f(x) = \sum_{j=1}^{p-1} \chi(j) x^j -\varepsilon \prod_{k=1}^{(p-1)/2}(x^{2k-1} - x^{p-(2k-1)}).$$
Then $f(0) = 0$ and  $f(\zeta) = 0$, therefore $(x^p-1)$ divides $f(x)$. As $f(x) \in \Z[x]$ and $x^p-1 \in \Z[x]$ is monic,  $f(x) = (x^p-1)h(x), h(x) \in \Z[x]$.
If we replace $x$ by $1+t$, we obtain
$$f(1+t) = \sum_{j=1}^{p-1} \chi(j) (1+t)^j -\varepsilon \prod_{k=1}^{(p-1)/2}\left((1+t)^{2k-1} - (1+t)^{p-(2k-1)}\right).$$
We compute the coefficient of $t^{(p-1)/2}$ in the polynomial $f(1+t)$ :
\begin{align*}
\sum_{j=1}^{p-1} \chi(j) (1+t)^j &= \sum_{j=1}^{p-1} \chi(j)  \sum_{i=1}^j \binom{j}{i}t^i\\
&= \sum_{i=1}^{p-1} \sum_{j=i}^{p-1} \chi(j) \binom{j}{i}t^i\\
\end{align*}
Thus the coefficient of $t^{(p-1)/2}$ in  $\sum\limits_{j=1}^{p-1} \chi(j) (1+t)^j$ is $\sum\limits_{j=(p-1)/2}^{p-1} \chi(j) \binom{j}{(p-1)/2}$.
\begin{align*}
\prod_{k=1}^{(p-1)/2}((1+t)^{2k-1} - (1+t)^{p-(2k-1)})& = \prod_{k=1}^{(p-1)/2} \left((1+ (2k-1) t ) - (1+(p-(2k-1)) t +t^2u(t)\right)\\
&=\prod_{k=1}^{(p-1)/2} \left((4k-2-p)t + t^2v(t)\right)\\
&=t^{(p-1)/2} \left(\prod_{k=1}^{(p-1)/2} (4k-2-p)\right) + t^{(p+1)/2} w(t),
\end{align*}
where $u(t),v(t),w(t)$ are polynomials. So the coefficient of $t^{(p-1)/2}$ in $f(1+t)$ is
$$c_{(p-1)/2} =  \sum\limits_{j=(p-1)/2}^{p-1} \chi(j) \binom{j}{(p-1)/2} - \varepsilon  \prod_{k=1}^{(p-1)/2} (4k-2-p) .$$
Furthermore, 
\begin{align*}
f(1+t) &= \left((1+t)^p-1\right) h(1+t)\\
&=\left[\sum_{i=1}^p \binom{p}{i} t^i\right] h(1+t)\\
&= \left[\sum_{i=1}^p i!\binom{p}{i} \frac{t^i}{i!}\right] h(1+t)\\
&= \left[\sum_{i=0}^p a_i \frac{t^i}{i!}\right] h(1+t),\\
\end{align*}
where $a_0 = 0, a_i = i!\binom{p}{i} = \frac{p!}{(p-i)!}$, so $p \mid a_i, i=0,\ldots,p-1$ : the conditions of Ex.21 are verified, so $f(1+t) = \sum_{i=0}^{p-1} c_i t^i$ is such that 
$c_{(p-1)/2} = p (A/B),\ p \nmid B$. Equating these two evaluations of $c_{(p-1)/2}$, we obtain
$$\sum\limits_{j=(p-1)/2}^{p-1} \chi(j) \binom{j}{(p-1)/2} - \varepsilon  \prod_{k=1}^{(p-1)/2} (4k-2-p) = p \frac{A}{B}, \quad p \nmid B.$$
Multiplying by $B (p-1)!/2$, we obtain, as $p\nmid B$,
\begin{align*}
\frac{(p-1)!}{2}  \sum_{j=(p-1)/2}^{p-1} \chi(j) \binom{j}{(p-1)/2} &\equiv  \varepsilon  \frac{(p-1)!}{2} \prod_{k=1}^{(p-1)/2} (4k-2) \\
&\equiv \varepsilon ( 2\cdot 4\cdot6\cdots(p-1)) \prod_{k=1}^{(p-1)/2} (2k-1) \
&\equiv \varepsilon (p-1)!\\
&\equiv -\varepsilon \pmod p
\end{align*}
To prove that $\varepsilon = +1$, it remains to prove
$$S:=\left(\frac{(p-1)}{2}\right)!  \sum_{j=(p-1)/2}^{p-1} \chi(j) \binom{j}{(p-1)/2} \equiv -1 \pmod p$$
The factor of $((p-1)/2)!$ cancels the denominator of $\binom j{(p-1)/2}$, which leaves
\begin{align*}
S &= \sum_{j=(p-1)/2}^{p-1} \chi(j) \cdot j (j-1) \cdots (j-\frac{p-1}{2} + 1)\\
&=\sum_{j=1}^{p-1} \chi(j) \cdot j (j-1) \cdots (j-\frac{p-1}{2} + 1).
\end{align*}
The last equality is justified because all terms for $j < \frac{p-1}{2}$ are zero. Collecting powers of $j$, this is
$$S = \sum_{j=1}^{p-1} \sum_{k=0}^{(p-1)/2} \chi(j) \, a_k j^k \equiv \sum_{k=0}^{(p-1)/2} a_k \sum_{j=1}^{p-1} j^{k + \frac{p-1}{2}} \pmod p$$
for some integers $a_k$. It's important to note that $a_{(p-1)/2} = 1$.

Now, we compute $\sum_{j=1}^{p-1} j^n$ mod $p$. Let $T$ denote this sum and let $g$ be a generator of $\Z/p^\times$. Then, for all positive integer $n$,
$$g^n T = \sum_{j=1}^{p-1} (gj)^n \equiv \sum_{k=1}^{p-1} k^n = T \pmod p.$$
Congruence holds because $gj$ also runs over a complete system of nonzero residues mod $p$. If $g^n \not \equiv 1$, that is if $p-1 \nmid n$, then $T \equiv 0 \pmod p$. If $g^n \equiv 1$, then $j^n \equiv 1$ for all $j$, hence $T \equiv p-1 \equiv -1 \pmod p$.

Returning to the previous sum, the only nonzero term modulo $p$ is $k = \frac{p-1}{2}$, so
$$S \equiv \sum_{k=0}^{(p-1)/2} a_k \sum_{j=1}^{p-1} j^{k + \frac{p-1}{2}} \equiv a_{(p-1)/2}\cdot (-1) = -1 \pmod p$$
as desired.
\end{proof}

\paragraph{Ex. 6.23}

{\it If $f(x) = x^n + a_1 x^{n-1} + \ldots + a_n$, $a_i \in \Z$, and $p$ is prime such that $p \mid a_i$ for $i = 1, \ldots, n$, and $p^2 \nmid a_n$, show that $f(x)$ is irreducible over $\Q$ (Eisenstein's irreducibility criterion).
}

\bigskip

{\bf Lemma.} If $f \in \Z[x], \deg(f) \geq 1,$ is not irreducible in $\Q[x]$, then there exist $g,h \in \Z[x] , \deg(g) \geq 1, \deg(h) \geq 1$ such that $f = gh$.
\begin{proof}(lemma)
Suppose that  $f(x)  = \sum\limits_{k=0}^n a_k x^k, a_k \in \mathbb{Z}$, is not irreducible in $\mathbb{Q}[x]$.

Then $f(x)= f_1(x)f_2(x) $, with $f_1,f_2 \in \mathbb{Q}[X]$, and $\deg(f_1)\geq 1, \deg(f_2) \geq 1$. As in Ex. 6.5, we can write $f_1(x) = \lambda p(x), f_2(x) = \mu q(x)$ where $\lambda, \mu \in \mathbb{Q}$, and $p,q \in \mathbb{Z}[X]$ are primitive. Let $\nu = \lambda \mu \in \Q$ : write $\nu = u/v, u\wedge v = 1, v \geq 1$. Then  $r(x) =  p(x)q(x) = \sum\limits_{k=0}^n c_k x^k$ is primitive (Ex. 6.4), and $f(x) = \frac{u}{v} r(x) =  \frac{u}{v} p(x)q(x)$.

As $vf(x) = ur(x)$, $v\mid uc_i,\ i=0,1,\ldots,n$, with $u \wedge v = 1$, so   $u \mid c_i$ for all $i$. The polynomial $r$ being primitive, $v \mid 1$, so $v = \varepsilon = \pm 1$.

Let $g(x) = \varepsilon u p(x), h(x)  = q(x)$.Then $g,h \in \Z[x]$,  $\deg(g)  \geq 1, \deg(h)  \geq 1$, and $f = gh$ is the product of  two non constant polynomials in  $\Z[x]$.

\end{proof}
\begin{proof}(Ex. 6.23) 

Let
$$
\varphi : 
\left\{
\begin{array}{ccc}
  \Z[x]&   \to & \F_p[x]  \\
  p(x)= a_0 +\cdots+a_n x^n& \mapsto  & \overline{p}(x) =  \overline{a_0}+\cdots+\overline{a_n}x^n,
\end{array}
\right.
$$
where $\overline{a_i}$ is the class of $a_i$ in $\F_p$.  $\varphi$ is a ring homomorphism.

We show that $f(x) = g(x) h(x),\  g,h \in \Z[x], \deg(g) \geq 1, \deg(h) \geq 1$ is impossible. Indeed in such a situation,
$$\overline{f}(x) = x^n = \overline{g}(x)\overline{h}(x).$$ 
As the only irreducible factor of $x^n$ is $x$, the unicity of the decomposition of a polynomial in irreducible factors in $\F_p[x]$ gives
$$\overline{g}(x) = \lambda x^i,\,  \overline{h}(x) = \mu x^j,\ \lambda, \mu \in \F_p, i,j \in \N.$$

As $\deg(\overline{g}) \leq \deg(g), \deg(\overline{h}) \leq \deg(h)$ and $\deg(\overline{g}) + \deg(\overline{h}) = n = \deg(f) + \deg(g)$, this implies that $i = \deg(\overline{f}) = \deg(f)$, $j=\deg(\overline{g}) = \deg(g)$, so $i\geq 1, j \geq 1$. Therefore $p \mid g(0), p \mid h(0)$, so $p^2 \mid a_n = g(0)h(0)$, which is in contradiction with the hypothesis.

From the lemma we deduce that $f(x)$ is irreducible in $\Q[x]$.
\end{proof}


\end{document}