quadratic_reciprocity_proofs.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage[makeroom]{cancel}
\usepackage{amssymb}
\usepackage{enumitem}

\title{Quadratic Reciprocity Proofs}
\author{Karim El Shenawy}
\date{February 2021}

\usepackage{natbib}
\usepackage{graphicx}

\begin{document}

\maketitle

\section*{Introduction}
This course notebook is the collection of theorem proofs, exercises and answers from Unit 7 of the Number Theory Through Inquiry (Mathematical Association of America Textbooks).

\section*{Theorems to Mark}

\subsection*{7.1 Theorem} 
\quad \textit{Let p be a prime and let a, b, and c be integers with a not divisible by p. Then there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ is equal to the set of solutions to a congruence of the form $x^2+b'x+c' \equiv 0 \;(\bmod\; p)$}

\begin{proof}
Suppose p is a prime and let a, b, and c $\in \mathbf{Z}$ with a not divisible by p. Assume that there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$. This implies that the value of $ax^2 + bx + c \in \mathbf{Z_p}$. Now, we know that $p \nmid a \Longrightarrow (a,p) = 1 \Longrightarrow a \equiv 1 \;(\bmod\; p)$. This also implies that the inverse of a exists $a^{-1} \in \mathbf{Z_p}$. Now by direct proof we can express $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ as
\begin{align*}
    && ax^2 + bx + c &\equiv 0 \;(\bmod\; p) &&\\
    && a^{-1}(ax^2 + bx + c) &\equiv 0\times a^{-1} \;(\bmod\; p) &&\\
    && x^2 + a^{-1}bx + a^{-1}c &\equiv 0 \;(\bmod\; p) &&\\
    && x^2 +b'x + c' &\equiv 0 \;(\bmod\; p) && \textbf{where $b' = a^{-1}b, c' = a^{-1}c$}
\end{align*}
Thus, if there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ is equal to the set of solutions to a congruence of the form $x^2+b'x+c' \equiv 0 \;(\bmod\; p)$.
\end{proof}


\subsection*{7.8 Theorem} 
\quad \textit{Suppose p is an odd prime and p does not divide either a or b. Then}
\begin{center}
    $(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$.
\end{center}

\begin{proof}
Suppose p is an odd prime and p does not divide either a or b.
\begin{itemize}
    \item Case 1: a and b are quadratic residues modulo p. Then by 7.7, ab is a quadratic residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && 1 &= 1 \times 1 &&\\
        && 1 &= 1 &&
    \end{align*}
    \item Case 2: a is quadratic residue modulo p and b is a quadratic non-residue modulo p. Then by 7.7, ab is a quadratic non-residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && -1 &= 1 \times -1 &&\\
        && 1 &= 1 &&
    \end{align*}
    \item Case 3: a and b are quadratic non-residues modulo p. Then by 7.7, ab is a quadratic residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && 1 &= -1 \times -1 &&\\
        && 1 &= 1 &&
    \end{align*}
\end{itemize}
\end{proof}



\subsection*{7.9 Theorem (Euler's Criterion)} 
\quad \textit{Suppose p is an odd prime and p does not divide the natural number a. Then a is a quadratic residue modulo p if and only if $a^{(p-1)/2} \equiv 1 \;(\bmod\; p)$; and a is quadratic non-residue modulo p if and only if $a^{(p-1)/2} \equiv -1 \;(\bmod\; p)$. This criterion can be abbreviation using the Legendre symbol:}
\begin{center}
    $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$.
\end{center}

\begin{proof}
Suppose p is an odd prime and p does not divide the natural number a.
\begin{itemize}
    \item Case 1: a is a quadratic residue modulo p. By definition, $\frac{a}{p} = 1$. Then by direct proof,
    \begin{align*}
        &\Longrightarrow x^2 \equiv a \;(\bmod\; p) (\Longrightarrow (x^2, p) = 1)&\\
        &\Longrightarrow x^{2\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow x^{2\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow x^{p-1} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\text{Since $(x^2, p) = 1$, then} (x, p) = 1&\\
        &(x, p) = 1 \Longrightarrow x^{p-1} \equiv 1 \;(\bmod\; p)& \textbf{By Fermat's Little Theorem}\\
        &\Longrightarrow x^{p-1} \equiv 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow \frac{a}{p} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p) \textbf{  since $\frac{a}{p} = 1$}&
    \end{align*}
    \item Case 2: a is a quadratic non-residue modulo p. By definition, $\frac{a}{p} = -1$. Then $x^2 \equiv a \;(\bmod\; p)$ has no solution. Suppose that for some integer x such that $1 \leq x < p$, there is $x^{-1}$ such that $1 \leq x^{-1} < p$ and $x \cdot x^{-1} \equiv a \;(\bmod\; p)$. Now since we know that $x^2 \equiv a \;(\bmod\; p)$ has no solution, this implies that $x \neq x^{-1}$. Therefore, by direct proof,
    \begin{align*}
        &&\prod_{j=1}^{\frac{p-1}{2}} x \cdot x^{-1}& \equiv \prod_{j=1}^{\frac{p-1}{2}} a \;(\bmod\; p)&&
        &&(p-1)! & \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&\\
        &&-1 & \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&\textbf{By Wilson's Theorem}\\
        &&\frac{a}{p} &\equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&
    \end{align*}
\end{itemize}
Therefore, for any natural number a while p is an odd prime and p does not divide a, then 
\begin{center}
    $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$.
\end{center}
\end{proof}

\subsection*{7.16 Theorem} 
\quad \textit{Let p be an odd prime, then}
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}

\begin{proof}
Let p be an odd prime, then
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}
The above can be then expressed as
\begin{center}
    $(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$.
\end{center}
Then, by direct proof,
\begin{itemize}
    \item Case 1: $\frac{2}{p} = 1$ when 2 is a quadratic residue modulo p
    \begin{align*}
    && (-1)^{\frac{p^2-1}{8}}&= (\frac{2}{p})&&\\
    && (-1)^{\frac{p^2-1}{8}}&= 1&& \textbf{By definition}\\
    && &\Longrightarrow \frac{p^2-1}{8} \equiv 0 \;(\bmod\; 2)&&\\
    && &\Longrightarrow \frac{p^2-1}{8} = 2k&&\textbf{$\exists k\in \mathbf{Z}$}\\
    && &\Longrightarrow p^2 = 16k + 1&&\\
    && &\Longrightarrow p^2 \equiv 1 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \sqrt{1} \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm1 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm1 \;(\bmod\; 8) &&
\end{align*}
    \item Case 2: $\frac{2}{p} = 1$ when 2 is a quadratic non-residue modulo p
    \begin{align*}
    && (-1)^{\frac{p^2-1}{8}}&= (\frac{2}{p})&&\\
    && (-1)^{\frac{p^2-1}{8}}&= -1 && \textbf{By definition}\\
    && &\Longrightarrow \frac{p^2-1}{8} \equiv 1 \;(\bmod\; 2)&&\\
    && &\Longrightarrow \frac{p^2-1}{8} = 2k + 1&&\textbf{$\exists k\in \mathbf{Z}$}\\
    && &\Longrightarrow p^2 = 16k + 9&&\\
    && &\Longrightarrow p^2 \equiv 9 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \sqrt{9} \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm3 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm3 \;(\bmod\; 8) &&
\end{align*}
\end{itemize}
Therefore, 
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv \pm1 \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv \pm3 \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}
\end{proof}

\subsection*{7.23 Theorem} 
\quad \textit{Let p be a prime congruent to 3 modulo 4. Let a be a natural number with $1<a<p-1$. Then a is quadratic residue modulo p if and only if $p-a$ is a quadratic non-residue modulo p.}

\begin{proof}
Let p be a prime congruent to 3 modulo 4. Let a be a natural number with $1<a<p-1$. Thus, $(p, a) = 1$. Suppose a is a quadratic residue modulo p, then
\begin{align*}
    &&a^{\frac{p-1}{2}} &\equiv 1 \;(\bmod\; p) && \textbf{By Euler's Criterion}\\
    &&a^{\frac{4k+2}{2}} &\equiv 1 \;(\bmod\; p) && p = 4k + 3, \exists k \in \mathbf{Z}\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&
\end{align*}
Similarly, suppose a is a quadratic non-residue modulo p, then
\begin{align*}
    &&a^{\frac{p-1}{2}} &\equiv -1 \;(\bmod\; p) && \textbf{By Euler's Criterion}\\
    &&a^{\frac{4k+2}{2}} &\equiv -1 \;(\bmod\; p) && p = 4k + 3, \exists k \in \mathbf{Z}\\
    &&a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv -1 \;(\bmod\; p) &&
\end{align*}
Now,
\begin{align*}
    &&(p-a)^{\frac{p-1}{2}} &\equiv (p-a)^{2k+1} \;(\bmod\; p) &&\\
    && &\equiv (0-a)^{2k+1} \;(\bmod\; p) && p \equiv 0 \;(\bmod\; p)\\
    && &\equiv -1^{2k+1}a^{2k+1} \;(\bmod\; p) && \\
    && &\equiv -1(1) \;(\bmod\; p) && \\
    && &\equiv -1 \;(\bmod\; p) && \\
\end{align*}
From this result we can conclude that (p-a) is quadratic non-residue modulo p.\\
Now, conversely, suppose that (p-a) is quadratic non-residue modulo p, then
\begin{align*}
    &&(p-a)^{\frac{p-1}{2}} &\equiv -1 \;(\bmod\; p) && \\
    &&(p-a)^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&-1^{2k+1}a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&-a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&\\
    &&a^{\frac{p-1}{2}} &\equiv 1 \;(\bmod\; p) &&
\end{align*}
Thus, by Euler's Criterion, a is a quadratic residue modulo p when (p-a) is quadratic non-residue modulo p.
\end{proof}

\subsection*{7.27 Theorem} 
\quad \textit{Let p be a prime and let i and j be natural numbers with $i \neq j$ satisfying $1 < i,j < \frac{p}{2}$. Then $i^2 \not\equiv j^2 \;(\bmod\; p)$.}

\begin{proof}
Let p be a prime and let i and j be natural numbers with $i \neq j$ satisfying $1 < i,j < \frac{p}{2}$. Suppose by contradiction, $i^2 \equiv j^2 \;(\bmod\; p) \Longrightarrow i^2 - j^2 \equiv (i-j)(i+j) \equiv 0\;(\bmod\; p)$. Thus, $p \mid (i-j)(i+j) \Longrightarrow p \mid (i-j)$ or $p \mid (i+j)$. However, since $1 < i,j < \frac{p}{2}$, then $i+j < p$ and $|i-j| < p$ which implies that p can not divide $(i+j)$ or $(i-j)$. Therefore $i^2 \not\equiv j^2 \;(\bmod\; p)$ holds.
\end{proof}

\section*{Practice Theorems from The Golden Rule: Quadratic Reciprocity}

\subsection*{7.1 Theorem} 
\quad \textit{Let p be a prime and let a, b, and c be integers with a not divisible by p. Then there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ is equal to the set of solutions to a congruence of the form $x^2+b'x+c' \equiv 0 \;(\bmod\; p)$}

\begin{proof}
Suppose p is a prime and let a, b, and c $\in \mathbf{Z}$ with a not divisible by p. Assume that there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$. This implies that the value of $ax^2 + bx + c \in \mathbf{Z_p}$. Now, we know that $p \nmid a \Longrightarrow (a,p) = 1 \Longrightarrow a \equiv 1 \;(\bmod\; p)$. This also implies that the inverse of a exists $a^{-1} \in \mathbf{Z_p}$. Now by direct proof we can express $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ as
\begin{align*}
    && ax^2 + bx + c &\equiv 0 \;(\bmod\; p) &&\\
    && a^{-1}(ax^2 + bx + c) &\equiv 0\times a^{-1} \;(\bmod\; p) &&\\
    && x^2 + a^{-1}bx + a^{-1}c &\equiv 0 \;(\bmod\; p) &&\\
    && x^2 +b'x + c' &\equiv 0 \;(\bmod\; p) && \textbf{where $b' = a^{-1}b, c' = a^{-1}c$}
\end{align*}
Thus, if there are integers b' and c' such that the set of solutions to the congruence $ax^2 + bx + c \equiv 0 \;(\bmod\; p)$ is equal to the set of solutions to a congruence of the form $x^2+b'x+c' \equiv 0 \;(\bmod\; p)$.
\end{proof}

\subsection*{7.2 Theorem} 
\quad \textit{Let p be a prime, and let b and c be integers. Then there exists a linear change of variable, $y = x+\alpha$ with $\alpha$ an integer, transforming the congruence $x^2 + bx + c \equiv 0 \;(\bmod\; p)$ into a congruence of the form $y^2 \equiv \beta \;(\bmod\; p)$ for some integer $\beta$.}

\begin{proof}
Given $p \in \mathbf{Z_p}$, and  $b, c \in \mathbf{Z}$. By theorem 7.1, we know that $x^2 + bx + c \equiv 0 \;(\bmod\; p)$. Now suppose that

\begin{itemize}
    \item $p \neq 2$. Then by direct proof,
\begin{align*}
    && x^2 + bx + c &\equiv 0 \;(\bmod\; p) &&\\
    && 4 \times (x^2 + bx + c) &\equiv 0\times 4 \;(\bmod\; p) &&\\
    && 4x^2 + 4bx + 4c + b^2 - b^2 &\equiv 0 \;(\bmod\; p) &&\\
    && 4x^2 + 4bx + b^2 + 4c  - b^2 &\equiv 0 \;(\bmod\; p) &&\\
    && (2x+b)^2 + 4c - b^2 &\equiv 0 \;(\bmod\; p) &&\\
    && (2x+b)^2 &\equiv b^2 - 4c \;(\bmod\; p) &&\\
    && y' &\equiv b^2 - 4c \;(\bmod\; p) &&\textbf{let $y' = (2x +b)^2$}
\end{align*}
Since, $y' = 2x +b$ and $p \nmid 2 \Longrightarrow (2,p) = 1 \Longrightarrow 2 \equiv 1 \;(\bmod\; p)$, this also implies that the inverse of a exists $2^{-1} \in \mathbf{Z_p}$. Now let $y = y'2^{-1} = (2x +b)(2^-1) = x + 2^{-1}b, \alpha = 2^{-1}b \in \mathbf{Z_p}$. Then $\alpha$ is an integer modulo p. This results to $y^2 \equiv \beta \;(\bmod\; p)$ for some integer $\beta = b^2 - 4c$.
    \item $p = 2$. Then either $x^2 \equiv 0 \;(\bmod\; p)$ or $x^2 \equiv 1 \;(\bmod\; p)$. This then implies that suppose $x=y$ then $y^2 \equiv \beta \;(\bmod\; p)$ for some integer $\beta$. 
\end{itemize}
\end{proof}

\subsection*{7.3 Theorem}
\quad \textit{Let p be an odd prime. Then half the numbers not congruent to 0 in any complete residue system modulo p are perfect square modulo p and half are not.}

\begin{proof}
Suppose p $p \in \mathbf{Z_p}, p \neq 2$. Then by Theorem 6.6 and 6.17, we know that every prime p has $\phi(p-1)$ primitive roots and that we can have a primitive root g for each p which forms a complete residue system modulo p as follows,
\begin{center}
    $\{0, 1, 2,...,p-1\} \equiv \{g^0, g, g^2, ..., g^{p-1}\}.$
\end{center}
Now since $p \neq 2$, then we can rewrite the above set $\{0, 1, g^2, g^4, g^6,..., g^{p-3}, g^{p-1}\}$ as $\{0, 1, g^2, (g^2)^2, (g^3)^2,..., g^{\frac{(p-3)}{2}^2},g^{\frac{(p-1)}{2}^2}\}$. This implies that there $\frac{p-1}{2}$ numbers in the set $\{0, 1, 2,...,p-1\}$ that are perfect square and each odd power of g can not be a perfect square. Thus, if $g^{2k+1}$ is perfect square then we have some $x \in \{1, 2,...,p-1\}$ such that $g^{2k+1} = x^2, 0 < 2k+1<p-1$.\\
Now since $x \in \{1, 2,...,p-1\}$, then $x = g^i, 0 < i \leq p-1$. Thus we have $g^{2k+1} = g^{2i} \Longrightarrow g^{2k+1-2i} \equiv 1 \;(\bmod\; p) \Longrightarrow p-1 \mid 1.$ However, this is a contradiction since p-1 is even and $2k+1-2i = 2(k+1)-i$ is odd. So, no odd power of g is a perfect square modulo p. Since $\{g^0, g, g^2, ..., g^{p-1}\}$ are the result of the powers of $\{0, 1, 2,...,p-1\}$. We can deduce that $\{0, 1, 2,...,p-1\}$ is half odd and half even. Thus, there are half the numbers not congruent to 0 in any complete residue system modulo p are perfect square modulo p and half are not.
\end{proof}

\subsection*{7.4 Exercise} 
\quad \textit{Determine which of the numbers $1,2,3,...,12$ are perfect squares modulo 13. For each such perfect square, list the number or numbers in the set whose square is that number.}

\begin{itemize}
    \item $1^2 \equiv 1 \;(\bmod\; 13)$
    \item $2^2 \equiv 4 \;(\bmod\; 13)$
    \item $3^2 \equiv 9 \;(\bmod\; 13)$
    \item $4^2 \equiv 3 \;(\bmod\; 13)$
    \item $5^2 \equiv 12 \;(\bmod\; 13)$
    \item $6^2 \equiv 10 \;(\bmod\; 13)$
    \item $7^2 \equiv 10 \;(\bmod\; 13)$
    \item $8^2 \equiv 12 \;(\bmod\; 13)$
    \item $9^2 \equiv 3 \;(\bmod\; 13)$
    \item $10^2 \equiv 9 \;(\bmod\; 13)$
    \item $11^2 \equiv 4 \;(\bmod\; 13)$
    \item $12^2 \equiv 1 \;(\bmod\; 13)$
\end{itemize}
Thus, the numbers that are perfect squares are 1, 4, 9, 3, 12, 10. 

\subsection*{7.5 Question} 
\quad \textit{Can you characterize perfect squares modulo a prime p in terms of their representation as a power of a primitive prime.}

\textit{Solution.} We know that for every prime p, there are $\phi(p-1)$ primitive roots, by Theorem 6.17. Suppose tha the set of all primitive roots modulo p is $\{a_0, a_1, a_2,...,a_{p-1}\}$.\\
Any number that is a perfect square can not be primitve root modulo p since $a_i$ is a square of any x thrn x can be written as power of $a_i \;(\bmod\; p)$. Hence for each x (perfect square), there exists $b_i \in \mathbf{Z}$ such that
\begin{center}
    $a_i^{b_i} \equiv x \;(\bmod\; p)$ if $b_i \mid \phi(p-1)$.
\end{center}

\subsection*{7.6 Theorem} 
\quad \textit{Let p be a prime. Then half the numbers not congruent to 0 modulo p in any complete residue system modulo p are quadratic residues modulo p and half are quadratic non-residues modulo p.}

\begin{proof}
Suppose $p \in \mathbf{Z_p}$. By Theorem 6.8, we know that for every prime, there exist at least 1 primitive root modulo p. Suppose that for p, that primitive root is g. Also we know that $(\frac{a}{b}) \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)$. Thus,
\begin{align*}
    && (\frac{a}{b}) &\equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&\\
    && (\frac{g^k}{b}) &\equiv g^{k\frac{p-1}{2}} \;(\bmod\; p)&& \textbf{$\exists k \in \mathbf{Z}$}
\end{align*}
Now, g is not a quadratic residue, hence $g^{p-1} \equiv 1 \;(\bmod\; p)$. Therefore, $(\frac{a}{b}) \equiv (-1)^k \;(\bmod\; p)$.\\
Moreover, we can suggest that 
\begin{center}
    $\sum_{a=1}^{b-1} (\frac{a}{b}) = \sum_{a=1}^{b-1} (-1)^k = 0$.
\end{center}
Therefore, half the numbers not congruent to 0 modulo p in any complete residue system modulo p are quadratic residues modulo p and half are quadratic non-residues modulo p.
\end{proof}

\subsection*{7.7 Theorem} 
\quad \textit{Suppose p is an odd prime and p does not divide either of the two integers a or b. Then}
\begin{enumerate}
    \item If a and b are both quadratic residues modulo p, then ab is a quadratic residue modulo p;
    \begin{proof}
    Given that p is an odd prime and p does not divide either of the two integers a or b. We know that $(\frac{a}{b}) = 1$ if and only if $(\frac{a}{b}) \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)$. Therefore, $a \equiv x^k \;(\bmod\; p), \exists  k \in \mathbf{Z}$ and $b \equiv y^k \;(\bmod\; p)$. This implies that $ab \equiv (xy)^k \;(\bmod\; p)$ then ab is a quadratic residue.
    \end{proof}
    \item If a is quadratic residue modulo p and b is a quadratic non-residue modulo p, then ab is a quadratic non-residue modulo p;
    \begin{proof}
    Given that p is an odd prime and p does not divide either of the two integers a or b. We know that $a^{\frac{p-1}{2}} \equiv 1 \;(\bmod\; p)$ and $b^{\frac{p-1}{2}} \equiv -1 \;(\bmod\; p)$. This implies that $(ab)^{\frac{p-1}{2}} \equiv (-1) \;(\bmod\; p)$ then ab is a not quadratic residue.
    \end{proof}
    \item If a and b are both quadratic non-residues modulo p, then ab is a quadratic residue modulo p.
    \begin{proof}
    Given that p is an odd prime and p does not divide either of the two integers a or b. We know that $a^{\frac{p-1}{2}} \equiv -11 \;(\bmod\; p)$ and $b^{\frac{p-1}{2}} \equiv -1 \;(\bmod\; p)$. This implies that $(ab)^{\frac{p-1}{2}} \equiv 1 \;(\bmod\; p)$ then ab is a quadratic residue.
    \end{proof}
\end{enumerate}

\subsection*{7.8 Theorem} 
\quad \textit{Suppose p is an odd prime and p does not divide either a or b. Then}
\begin{center}
    $(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$.
\end{center}

\begin{proof}
Suppose p is an odd prime and p does not divide either a or b.
\begin{itemize}
    \item Case 1: a and b are quadratic residues modulo p. Then by 7.7, ab is a quadratic residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && 1 &= 1 \times 1 &&\\
        && 1 &= 1 &&
    \end{align*}
    \item Case 2: a is quadratic residue modulo p and b is a quadratic non-residue modulo p. Then by 7.7, ab is a quadratic non-residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && -1 &= 1 \times -1 &&\\
        && 1 &= 1 &&
    \end{align*}
    \item Case 3: a and b are quadratic non-residues modulo p. Then by 7.7, ab is a quadratic residue. Thus by direct proof,
    \begin{align*}
        && (\frac{ab}{p}) &= (\frac{a}{p})(\frac{b}{p}) &&\\
        && 1 &= -1 \times -1 &&\\
        && 1 &= 1 &&
    \end{align*}
\end{itemize}
\end{proof}

\subsection*{7.9 Theorem (Euler's Criterion)} 
\quad \textit{Suppose p is an odd prime and p does not divide the natural number a. Then a is a quadratic residue modulo p if and only if $a^{(p-1)/2} \equiv 1 \;(\bmod\; p)$; and a is quadratic non-residue modulo p if and only if $a^{(p-1)/2} \equiv -1 \;(\bmod\; p)$. This criterion can be abbreviation using the Legendre symbol:}
\begin{center}
    $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$.
\end{center}

\begin{proof}
Suppose p is an odd prime and p does not divide the natural number a.
\begin{itemize}
    \item Case 1: a is a quadratic residue modulo p. By definition, $\frac{a}{p} = 1$. Then by direct proof,
    \begin{align*}
        &\Longrightarrow x^2 \equiv a \;(\bmod\; p) (\Longrightarrow (x^2, p) = 1)&\\
        &\Longrightarrow x^{2\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow x^{2\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow x^{p-1} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\text{Since $(x^2, p) = 1$, then} (x, p) = 1&\\
        &(x, p) = 1 \Longrightarrow x^{p-1} \equiv 1 \;(\bmod\; p)& \textbf{By Fermat's Little Theorem}\\
        &\Longrightarrow x^{p-1} \equiv 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow 1 \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&\\
        &\Longrightarrow \frac{a}{p} \equiv a^{\frac{p-1}{2}} \;(\bmod\; p) \textbf{  since $\frac{a}{p} = 1$}&
    \end{align*}
    \item Case 2: a is a quadratic non-residue modulo p. By definition, $\frac{a}{p} = -1$. Then $x^2 \equiv a \;(\bmod\; p)$ has no solution. Suppose that for some integer x such that $1 \leq x < p$, there is $x^{-1}$ such that $1 \leq x^{-1} < p$ and $x \cdot x^{-1} \equiv a \;(\bmod\; p)$. Now since we know that $x^2 \equiv a \;(\bmod\; p)$ has no solution, this implies that $x \neq x^{-1}$. Therefore, by direct proof,
    \begin{align*}
        &&\prod_{j=1}^{\frac{p-1}{2}} x \cdot x^{-1}& \equiv \prod_{j=1}^{\frac{p-1}{2}} a \;(\bmod\; p)&&
        &&(p-1)! & \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&\\
        &&-1 & \equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&\textbf{By Wilson's Theorem}\\
        &&\frac{a}{p} &\equiv a^{\frac{p-1}{2}} \;(\bmod\; p)&&
    \end{align*}
\end{itemize}
Therefore, for any natural number a while p is an odd prime and p does not divide a, then 
\begin{center}
    $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$.
\end{center}
\end{proof}

\subsection*{7.10 Theorem} 
\quad \textit{Let p be an odd prime. Then $-1$ is a quadratic residue modulo p if and only if p is of the form $4k+1$ for some integer k. Or, equivalently,}
\begin{center}
    $(\frac{-1}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv 1 \;(\bmod\; 4)\\
          -1 \quad &\text{if} \, p \equiv 3 \;(\bmod\; 4)\\
     \end{cases}$.
\end{center}

\begin{proof}
Suppose $p \in \mathbf{Z_p}$. Then by Theorem 7.9, $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$ if p does not divide natural number a. Now we know that p does not divide -1, then $-1^{(p-1)/2} \equiv (\frac{-1}{p}) \equiv -1 \;(\bmod\; p)$ if and only if -1 is a quadratic residue modulo p. This holds if and only if the exponent $\frac{p-1}{2}$ is an even integer which can be expressed as $\frac{p-1}{2} \equiv 0 \;(\bmod\; 2)$ or $\frac{p-1}{2} \equiv 0 \;(\bmod\; 4)$. Now by direct proof,
\begin{align*}
    &\frac{p-1}{2} \equiv 0 \;(\bmod\; 4) &\\
    &p \equiv 1 \;(\bmod\; 4) &\\
    &\Longrightarrow p = 4k + 1, \exists k \in \mathbf{Z}&&
\end{align*}
Therefore, p is of the form $4k+1$ for some integer k when $-1$ is a quadratic residue modulo p.
\end{proof}

\subsection*{7.11 Theorem} 
\quad \textit{Let k be a natural number and $p = 4k+1$ be a prime congruent to 1 modulo 4. Then}
\begin{center}
    $(\pm(2k)!)^2 \equiv -1 \;(\bmod\; p)$.
\end{center}

\begin{proof}
Suppose k is a natural number and $p = 4k+1$ is a prime congruent to 1 modulo 4. By Wilson's Theorem, we know that $(p-1)! \equiv -1 \;(\bmod\; p)$. Now suppose residue classes in the interval of $[-2k, 2k]$, then by Wilson's Theorem, $(-1)^{2k}(2k)!(2k)! \equiv -1 \;(\bmod\; p)$ or $((2k)!)^2 \equiv -1 \;(\bmod\; p)$. We also know that the negative square root of -1 is also the square root of -1 thus both of the following holds $(-(2k)!)^2 \equiv ((2k)!)^2 \equiv -1 \;(\bmod\; p)$, thus $(\pm(2k)!)^2 \equiv -1 \;(\bmod\; p)$.
\end{proof}

\subsection*{7.12 Theorem (Infinitude of $4k+1$ Primes Theorem)} 
\quad \textit{There are infinitely many primes congruent to 1 modulo 4.}\\
\textit{Hint: if $p_1, p_2,...,p_r$ are primes each congruent to 1 modulo 4, what can you say about each prime factor of the number $N = (2p_1p_2\cdot\cdot\cdot p_r)^2 + 1$?}

\begin{proof}
Assume that there are primes each congruent to 1 modulo 4, $p_1, p_2,..., p_r$. Consider $N = (2p_1p_2...p_r)^2 + 1$. Let p be a prime that divides N. The prime p is relative prime to $2, p_1, p_2,...p_r$, so it is not 2 and is not congruent to 1 modulo 4. But $(2, p_1, p_2,...p_r)^2 \equiv -1 \;(\bmod\; p)$, so -1 is a quadratic residue modulo p. This contradicts Theorem 7.9, so there cannot be finitely many primes congruent to 1 modulo 4.
\end{proof}

\subsection*{7.13 Lemma} 
\quad \textit{Let p be a prime, a an integer not divisible by p, and $r_1, r_2,...,r_{\frac{(p-1)}{2}}$ the representative of $a,2a,...,\frac{p-1}{2}a$ in the complex residue system}
\begin{center}
    $\{-\frac{p-1}{2},...,-1,0,1,...,\frac{p-1}{2}\}$.
\end{center}
\textit{Then}
\begin{center}
    $a \cdot 2a \cdot ... \cdot \frac{p-1}{2}a \equiv (-1)^g(\frac{p-1}{2})! \;(\bmod\; p)$
\end{center}
\textit{where g is the number of $r_i$'s which are negative.}\\
\textit{Hint: It suffices to show that we never have $r_i \equiv -1r_j \;(\bmod\; p)$ for some i and j.}

\begin{proof}
Let p be a prime, a an integer not divisible by p, and $r_1, r_2,...,r_{\frac{(p-1)}{2}}$ the representative of $a,2a,...,\frac{p-1}{2}a$ in the complex residue system
\begin{center}
    $\{-\frac{p-1}{2},...,-1,0,1,...,\frac{p-1}{2}\}$.
\end{center}
Suppose $\exists i, j \in \mathbf{Z}$ where $1 \leq i, j \leq \frac{p-1}{2}$ then with $ia \not\equiv ja \;(\bmod\; p)$ implies that $i-j \leq \frac{p-1}{2} < p$. Now, suppose that $r_i \equiv -r_j\;(\bmod\; p)$ for some i and j. Then $ax \equiv ay \;(\bmod\; p)$ where $r_i \equiv ax \;(\bmod\; p)$ and $-r_j \equiv ay \;(\bmod\; p)$, where $-\frac{p-1}{2} \leq k,a\leq \frac{p-1}{2}$. This implies that $p \mid (x-y)a$ but this is a contradiction since $p \nmid a$ and $p \nmid x-y$ since $x-y < p$. Therefore, $r_i \not\equiv -r_j\;(\bmod\; p)$ for some i and j.\\
Thus, 
\begin{align*}
    && r_1r_2 \cdot ...\cdot r_{\frac{p-1}{2}} &= (-1)^g (1 \cdot 2 \cdot ... \cdot \frac{p-1}{2})&&\\
    && & \textbf{g is number of negative $r_i$}&&\\
    && &= (-1)^g (\frac{p-1}{2})! \;(\bmod\; p)&&\\
    && & \textbf{Since, there are $\frac{p-1}{2}$ and $r_i \not\equiv -r_j\;(\bmod\; p)$}&&
\end{align*}
\end{proof}

\subsection*{7.14 Theorem (Gauss' Lemma)} 
\quad \textit{Let p be a prime and a an integer not divisible by p. Let g be the number of representatives of $a,2a,...,\frac{p-1}{2}a$ in the complex system residue\\ $\{-\frac{p-1}{2},...,-1,0,1,...,\frac{p-1}{2}\}$. Then}
\begin{center}
    $(\frac{a}{p}) = (-1)^g$.
\end{center}

\begin{proof}
Given that p is be a prime and a an integer not divisible by p, a is relatively prime to p, $a_i \equiv \pm a_j \;(\bmod\; p)$ if and only if $i \neq \pm j \;(\bmod\; p)$. Since $1 \leq i,j \leq \frac{p-1}{2}$, this congruence can only hold if $i = j$. Therefore, $a \cdot 2a \cdot ... \cdot \frac{p-1}{2}a \equiv (-1)^g(\frac{p-1}{2})! \;(\bmod\; p)$, where g is the number of representatives that are negative. Since $(\frac{p-1}{2})!$ is relatively prime to p, $a^{\frac{p-1}{2}} (-1)^g \;(\bmod\; p)$. By Theorem 7.9, a is a quadratic residue if and only if $(-1)^g = 1$.
\end{proof}

\subsection*{7.15 Question} 
\quad \textit{Does the prime's residue class modulo 4 determine whether or not 2 is a quadratic residue? Consider the primes' residue class modulo 8 and see whether the residue class seems to correlate with whether or not 2 is a quadratic residue. Make a conjecture.}

\textbf{Conjecture.} \textit{Let p be a prime and a an integer not divisible by p. Then the prime's residue class modulo 4 determine whether or not 2 is a quadratic residue} Incomplete

\subsection*{7.16 Theorem} 
\quad \textit{Let p be an odd prime, then}
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}

\begin{proof}
Let p be an odd prime, then
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}
The above can be then expressed as
\begin{center}
    $(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$.
\end{center}
Then, by direct proof,
\begin{itemize}
    \item Case 1: $\frac{2}{p} = 1$ when 2 is a quadratic residue modulo p
    \begin{align*}
    && (-1)^{\frac{p^2-1}{8}}&= (\frac{2}{p})&&\\
    && (-1)^{\frac{p^2-1}{8}}&= 1&& \textbf{By definition}\\
    && &\Longrightarrow \frac{p^2-1}{8} \equiv 0 \;(\bmod\; 2)&&\\
    && &\Longrightarrow \frac{p^2-1}{8} = 2k&&\textbf{$\exists k\in \mathbf{Z}$}\\
    && &\Longrightarrow p^2 = 16k + 1&&\\
    && &\Longrightarrow p^2 \equiv 1 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \sqrt{1} \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm1 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm1 \;(\bmod\; 8) &&
\end{align*}
    \item Case 2: $\frac{2}{p} = 1$ when 2 is a quadratic non-residue modulo p
    \begin{align*}
    && (-1)^{\frac{p^2-1}{8}}&= (\frac{2}{p})&&\\
    && (-1)^{\frac{p^2-1}{8}}&= -1 && \textbf{By definition}\\
    && &\Longrightarrow \frac{p^2-1}{8} \equiv 1 \;(\bmod\; 2)&&\\
    && &\Longrightarrow \frac{p^2-1}{8} = 2k + 1&&\textbf{$\exists k\in \mathbf{Z}$}\\
    && &\Longrightarrow p^2 = 16k + 9&&\\
    && &\Longrightarrow p^2 \equiv 9 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \sqrt{9} \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm3 \;(\bmod\; 16) &&\\
    && &\Longrightarrow p \equiv \pm3 \;(\bmod\; 8) &&
\end{align*}
\end{itemize}
Therefore, 
\begin{center}
    $(\frac{2}{p}) = \begin{cases}
          1 \quad &\text{if} \, p \equiv \pm1 \equiv 1 \text{ or } 7\;(\bmod\; 8),\\
          -1 \quad &\text{if} \, p \equiv \pm3 \equiv 3 \text{ or } 5 \;(\bmod\; 8).\\
     \end{cases}$.
\end{center}
\end{proof}

\subsection*{7.17 Exercise} 
\quad \textit{Table 1 shows $(\frac{p}{q})$ for the first several odd primes. For example, the table indicates $(\frac{7}{3}) = 1$, but that $(\frac{3}{7}) = -1$. Make another table that shows when $(\frac{p}{q}) = (\frac{q}{p})$ and when $(\frac{p}{q} \neq (\frac{q}{p})$.}

Done manually on book.

\subsection*{7.18 Exercise} 
\quad \textit{Make a conjecture about the relationship between $(\frac{p}{q})$ and $(\frac{q}{p})$ depending on p and q.}

\textbf{Conjecture.} \textit{Let p and q be odd primes, then $(\frac{p}{q})$ and $(\frac{q}{p})$ if p is a quadratic residue modulo q and q is a quadratic residue modulo p. Also if p is a quadratic non-residue modulo q and p is a quadratic non-residue modulo p.}

\subsection*{7.19 Theorem (Quadratic Reciprocity Theorem-Reciprocity Part)} 
\quad \textit{Let p and q be odd primes, then}
\begin{center}
    $(\frac{p}{q}) = \begin{cases}
          (\frac{q}{p}) \quad &\text{if} \, p \equiv 1 \;(\bmod\; 4) \text{ or } q \equiv 1 \;(\bmod\; 4),\\
          -(\frac{q}{p}) \quad &\text{if} \, p \equiv q \equiv 3 \;(\bmod\; 4).\\
     \end{cases}$.
\end{center}
\textit{Hint: Try to use the techniques used in the case of $(\frac{2}{p})$.}

\begin{proof}
Let p and q be odd primes. Suppose x is the number of pairs $(a, b), 1 \leq a \leq \frac{q-1}{2}$ such that $-\frac{q}{2} < ap - bq < 0$. Also, for each a, if there is a b for which $ap - bq$ satisfies this pairs of inequalities, then b is unique and $0 \leq a \leq \frac{p}{2}$. By Gauss' Lemma, $(p \mid q) = (-1)^x$.\\

Similarly, let y be the number of pairs $(a, b), 1 \leq b \leq \frac{p-1}{2}$ such that $-\frac{p}{2} < bq - ap < 0$. For each b, there is at most one value of a for which $bq - ap$ satisfies this pair of inequalities, and $0 < a < \frac{q}{2}$. By Gauss’s Lemma, $(b \mid a) = (-1)^y$. Therefore, $(a \mid b)(b \mid a) = (-1)^{x+y}$ where $x + y$ is the number of pairs $(a, b)$ such that $0 < a < \frac{q}{2}, 0 < n < \frac{p}{2}$, and $-\frac{2}{2} < ap - bq < \frac{p}{2}$.\\

If $(a, b)$ is such a pair, then $(\frac{q-1}{2} - a, \frac{p-1}{2} - b)$ also satisfies these inequalities. These two pairs are distinct unless $a = \frac{q+1}{4} and b = \frac{p+1}{4}$, which can happen if and only if $p \equiv q \equiv 3 \;(\bmod\; 4)$. Therefore, $x+y$ is even unless $p \equiv q \equiv 3 \;(\bmod\; 4)$, in which case $x+y$ is odd.
\end{proof}

\subsection*{7.20 Exercise (Computational Technique)} 
\quad \textit{Given a prime p, show how you can determine whether a number a is quadratic residue modulo p. Equivalently, show how to find $(\frac{a}{p})$. To illustrate your method, compute $(\frac{1248}{93})$ and some other examples.}

\begin{proof}
Let p be a prime and a be an integer such that $p \nmid a$. a is said to be a quadratic residue modulo p if there exists some integer x such that
\begin{center}
    $x^2 \equiv a \;(\bmod\; p)$.
\end{center}
We also know that the Legendre Symbol pf a mod p is
\begin{center}
    $a^{(p-1)/2} \equiv (\frac{a}{p}) \;(\bmod\; p)$.
\end{center}
Also by definition, we know that $(\frac{a}{p}) = 1$ if a is quadratic residue modulo p and $(\frac{a}{p}) = -1$ if a is quadratic non-residue modulo p. Moreover, by the fundamental theorem of arithmetic, we can express a natural number say n as a product of primes such as $n = p_1^{r_1}p_2^{r_2}...p_t^{r_t}$. Then $(\frac{a}{n}) = (\frac{a}{p_1})^{r_1}(\frac{a}{p_2})^{r_2}...(\frac{a}{p_t})^{r_t}$. This is called Jacobi Symbol.\\
If $(\frac{a}{n}) = -1$, then a is a quadratic non-residue modulo n. Thus,
\begin{center}
    $(\frac{1248}{93}) = (\frac{1248}{31}) (\frac{1248}{3}) = (\frac{8}{31})(\frac{0}{3}) = 0$.
\end{center}
Therefore, 1248 is a quadratic non-residue modulo 93.
\end{proof} 

\subsection*{7.21 Exercise} 
\quad \textit{Find all the quadratic residues modulo 23.}
\begin{center}
    $x^2  \equiv a \;(\bmod\; 23)$
\end{center}
\begin{itemize}
    \item $1^2 \equiv 1 \;(\bmod\; 23)$
    \item $2^2 \equiv 4 \;(\bmod\; 23)$
    \item $3^2 \equiv 9 \;(\bmod\; 23)$
    \item $4^2 \equiv 16 \;(\bmod\; 23)$
    \item $5^2 \equiv 2 \;(\bmod\; 23)$
    \item $6^2 \equiv 13 \;(\bmod\; 23)$
    \item $7^2 \equiv 3 \;(\bmod\; 23)$
    \item $8^2 \equiv 18 \;(\bmod\; 23)$
    \item $9^2 \equiv 12 \;(\bmod\; 23)$
    \item $10^2 \equiv 8 \;(\bmod\; 23)$
    \item $11^2 \equiv 6 \;(\bmod\; 23)$
    \item $12^2 \equiv 6 \;(\bmod\; 23)$
    \item $13^2 \equiv 8 \;(\bmod\; 23)$
    \item $14^2 \equiv 12 \;(\bmod\; 23)$
    \item $15^2 \equiv 18 \;(\bmod\; 23)$
    \item $16^2 \equiv 3 \;(\bmod\; 23)$
    \item $17^2 \equiv 13 \;(\bmod\; 23)$
    \item $18^2 \equiv 2 \;(\bmod\; 23)$
    \item $19^2 \equiv 16 \;(\bmod\; 23)$
    \item $20^2 \equiv 9 \;(\bmod\; 23)$
    \item $21^2 \equiv 4 \;(\bmod\; 23)$
    \item $22^2 \equiv 1 \;(\bmod\; 23)$
\end{itemize}
Thus the set of quadratic residue modulo 23 is $\{1,4,9,16,2,13,3,18,12,8,6\}$

\subsection*{7.22 Theorem} 
\quad \textit{Let p be a prime of the form $p=2q+1$ where q is a prime. Then every natural number a, $0<a<p-1$, is either a quadratic residue or a primitive root modulo p.}

\begin{proof}

\end{proof}

\subsection*{7.23 Theorem} 
\quad \textit{Let p be a prime congruent to 3 modulo 4. Let a be a natural number with $1<a<p-1$. Then a is quadratic residue modulo p if and only if $p-a$ is a quadratic non-residue modulo p.}

\begin{proof}
Let p be a prime congruent to 3 modulo 4. Let a be a natural number with $1<a<p-1$. Thus, $(p, a) = 1$. Suppose a is a quadratic residue modulo p, then
\begin{align*}
    &&a^{\frac{p-1}{2}} &\equiv 1 \;(\bmod\; p) && \textbf{By Euler's Criterion}\\
    &&a^{\frac{4k+2}{2}} &\equiv 1 \;(\bmod\; p) && p = 4k + 3, \exists k \in \mathbf{Z}\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&
\end{align*}
Similarly, suppose a is a quadratic non-residue modulo p, then
\begin{align*}
    &&a^{\frac{p-1}{2}} &\equiv -1 \;(\bmod\; p) && \textbf{By Euler's Criterion}\\
    &&a^{\frac{4k+2}{2}} &\equiv -1 \;(\bmod\; p) && p = 4k + 3, \exists k \in \mathbf{Z}\\
    &&a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv -1 \;(\bmod\; p) &&
\end{align*}
Now,
\begin{align*}
    &&(p-a)^{\frac{p-1}{2}} &\equiv (p-a)^{2k+1} \;(\bmod\; p) &&\\
    && &\equiv (0-a)^{2k+1} \;(\bmod\; p) && p \equiv 0 \;(\bmod\; p)\\
    && &\equiv -1^{2k+1}a^{2k+1} \;(\bmod\; p) && \\
    && &\equiv -1(1) \;(\bmod\; p) && \\
    && &\equiv -1 \;(\bmod\; p) && \\
\end{align*}
From this result we can conclude that (p-a) is quadratic non-residue modulo p.\\
Now, conversely, suppose that (p-a) is quadratic non-residue modulo p, then
\begin{align*}
    &&(p-a)^{\frac{p-1}{2}} &\equiv -1 \;(\bmod\; p) && \\
    &&(p-a)^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&-1^{2k+1}a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&-a^{2k+1} &\equiv -1 \;(\bmod\; p) &&\\
    &&a^{2k+1} &\equiv 1 \;(\bmod\; p) &&\\
    &&a^{\frac{p-1}{2}} &\equiv 1 \;(\bmod\; p) &&
\end{align*}
Thus, by Euler's Criterion, a is a quadratic residue modulo p when (p-a) is quadratic non-residue modulo p.
\end{proof}

\subsection*{7.24 Theorem} 
\quad \textit{Let p be a prime of the form $p=2q+1$ where q is an odd prime. Then $p \equiv 3 \;(\bmod\; 4)$.}

\begin{proof}
Given that p is a prime of the form $p=2q+1$ where q is an odd prime. Since q is prime, we can express $q = 2k+1,\exists k \in \mathbf{Z}$. Then, by direct proof,
\begin{align*}
    &&p &= 2q + 1&&\\
    &&p &= 2(2k+1) + 1&&\textbf{q = 2k + 1}\\
    &&p &= 4k+3&&\\
    &&p &\equiv 4k+3 \;(\bmod\; 4)&&\\
    &&p &\equiv 3 \;(\bmod\; 4)&& \textbf{since $4 \mid 4k$}
\end{align*}
\end{proof}

\subsection*{7.25 Theorem} 
\quad \textit{Let p be a prime of the form $p=2q+1$ where q is an odd prime. Let a be a natural number, $1<a<p-1$. Then a is a quadratic residue if and only if $p-a$ is a primitive root modulo p.}

\begin{proof}
Given that p is a prime of the form $p=2q+1$ where q is an odd prime. By Theorem 7.24, $p = 2q + 1 \equiv 3 \;(\bmod\; 4)$. Therefore, if a is a quadratic residue, then $p-a$ is a quadratic non-residue. The order of $p-a$ must divide $p-1 = 2q$, and therefore it must be $1,2,q,$ or $2q$. Since the only residue of order 1 is 1 and the only residue of order 2 is $p-1$ and $1 < p-a < p-1$, the order of $p-a$ must be $q$ or $2q$. Since $p-a$is quadratic non-residue, $(p-a)^{\frac{p-1}{2}} \equiv -1 \;(\bmod\; p)$. Since $\frac{p-1}{2} = q$, the order of $p-a$ is not q. Therefore, the order of $p - a$ is $2q = p - 1$, so $p - a$ is a primitive root.\\

If $p - a$ is a primitive root, then $(p - a)^{\frac{(p-1)}{2}} 6 \equiv 1 \;(\bmod\; p)$, which implies that $p - a$ is
not a quadratic residue. Since $p \equiv 3 \;(\bmod\; 4)$, a must be a quadratic residue modulo p.
\end{proof}

\subsection*{7.26 Theorem} 
\quad \textit{Let p be a prime and a be an integer. Then $a^2$ is not a primitive root modulo p.}

\begin{proof}
Let p be a prime and a be an integer. By contradiction, suppose $a^2$ is a primitive root modulo p. Then, $ord_p(a^2) = p-1$, by direct proof,
\begin{align*}
    &&(a^2)^{p-1} &\equiv 1 \;(\bmod\; p)&&\textbf{By Fermat's Little Theorem}\\
    &&(a)^{2(p-1)} - 1&\equiv 0 \;(\bmod\; p)&&\\
    &&(a^{p-1} - 1)(a^{p-1} + 1)&\equiv 0 \;(\bmod\; p)&&
\end{align*}
Since p is prime then $p \mid (a^{p-1} - 1)$ or/and $p \mid (a^{p-1} + 1)$.
\begin{itemize}
    \item Case 1: Suppose $p \mid (a^{p-1} - 1)$. This implies that $a^{p-1} \equiv 1 \;(\bmod\; p) \Longrightarrow ord_p(a) \mid p-1 \Longrightarrow ord_p(a^2) = p - 1$ where p-1 is even. Then $ ord_p(a) = p - 1 \not\Longrightarrow  ord_p(a^2) = p - 1$ which is a contradiction.
    \item Case 2: Suppose $p \mid (a^{p-1} + 1)$. This implies that
    \begin{align*}
        &&a^{p-1} &\equiv -1 \;(\bmod\; p)&&\\
        &&a^{2(p-1)} &\equiv -1^2 \;(\bmod\; p)&&\\
        &&(a^2)^{(p-1)} &\equiv -1 \;(\bmod\; p)&&\\
    \end{align*}
    Thus, $ord_p(a) = 2(p-1)$ which is not possible since (p-1, a) = 1.
\end{itemize}
Therefore. $ord_p(a^2) = p-1$ is not possible thus $a^2$ is not a primitive root of p.
\end{proof}

\subsection*{7.27 Theorem} 
\quad \textit{Let p be a prime and let i and j be natural numbers with $i \neq j$ satisfying $1 < i,j < \frac{p}{2}$. Then $i^2 \not\equiv j^2 \;(\bmod\; p)$.}

\begin{proof}
Let p be a prime and let i and j be natural numbers with $i \neq j$ satisfying $1 < i,j < \frac{p}{2}$. Suppose by contradiction, $i^2 \equiv j^2 \;(\bmod\; p) \Longrightarrow i^2 - j^2 \equiv (i-j)(i+j) \equiv 0\;(\bmod\; p)$. Thus, $p \mid (i-j)(i+j) \Longrightarrow p \mid (i-j)$ or $p \mid (i+j)$. However, since $1 < i,j < \frac{p}{2}$, then $i+j < p$ and $|i-j| < p$ which implies that p can not divide $(i+j)$ or $(i-j)$. Therefore $i^2 \not\equiv j^2 \;(\bmod\; p)$ holds.
\end{proof}

\subsection*{7.28 Theorem} 
\quad \textit{Let p be a prime of the form $p=2q+1$ where q is an odd prime. Then the complete set of numbers that are not primitive roots modulo p are $1,-1,2^2,3^2,...,q^2$.}

\begin{proof}
Let p be a prime of the form $p=2q+1$ where q is an odd prime. Suppose that the complete set of numbers that are not primitive roots modulo p are $1,-1,2^2,3^2,...,q^2$. Then, by direct proof,
\begin{itemize}
    \item $(q+1)^2 \equiv q^2 + 2q + 1 \equiv q^2 \;(\bmod\; p)$
    \item $(q+2)^2 \equiv (q+1)^2 + 2(q+1) + 1 \equiv q^2 + 2 \;(\bmod\; p)$
    \item $(q-1)^2 \equiv q^2 - 2q + 1 \equiv q^2 + 2 \;(\bmod\; p)$
    \item Thus, $(q+2)^2 \equiv (q^2-1)^2 \;(\bmod\; p)$
    \item $(q+3)^2 \equiv (q+2)^2 + 2(q+2) + 1 \equiv q^2+6 \;(\bmod\; p)$
    \item $(q-2)^2 \equiv q^2 + 4q + 1 \equiv q^2+6 \;(\bmod\; p)$
    \item Thus, $(q+3)^2 \equiv (q^2-2)^2 \;(\bmod\; p)$
\end{itemize}
Now,
\begin{center}
    $(2q)^2 \equiv 4q^2 \equiv -4q-1 \equiv 1 \;(\bmod\; p)$
\end{center}
Therefore,  $1,-1,2^2,3^2,...,q^2$ are the complete set of numbers that are not primitive roots modulo p.
\end{proof}

Alternate Proof:
\begin{proof}
Let p be a prime of the form $p=2q+1$ where q is an odd prime. Suppose that the complete set of numbers that are not primitive roots modulo p are $1,-1,2^2,3^2,...,q^2$. Since for any $a \in \{2,3,..,q-1\}$ then $(a^2)^b \equiv a^{2b} \equiv a^{q-1} \equiv 1 \;(\bmod\; q)$, thus $ord_p(a^2) = p < q$ which implies that $a^2$ is not a primitive root modulo q. 
\end{proof}

\subsection*{7.29 Theorem} 
\quad \textit{Let p be a prime of the form $p=2q+1$ where q is an odd prime. Then the complete set of numbers that are primitive roots modulo are $-2^2,-3^2,...,-q^2$.}

\begin{proof}
Let p be a prime of the form $p=2q+1$ where q is an odd prime. Suppose the complete set of numbers that are primitive roots modulo are $-2^2,-3^2,...,-q^2$. Then p is odd prime so for any $a \in \{2,3,...,q-1\}$. Now $(-a)^2p \equiv -1 \;(\bmod\; q)$ so $-a^2$ is a primitive root modulo p.\\
Now, we must prove that the set $-2^2,-3^2,...,-q^2$ contains all primitive roots and the set $1,-1,2^2,3^2,...,q^2$ contains all non-primitive roots (By Theorem 7.28). If we prove that the union of both these sets forms $\mathbf{Z_q}$. Then we are done. Now note that for $a \neq b$ then 
\begin{align*}
    &&\Longrightarrow a^2 &\equiv b^2 \;(\bmod\; q) && a,b \in \{1,2,3,..,q-1\}\\
    &&\Longrightarrow a &\equiv -b \;(\bmod\; q) &&
\end{align*}
So,
\begin{center}
    $\{1^2,2^2,3^2,..,(q-1)^2\} = \frac{q-1}{2} = p$.
\end{center}
Similarly,
\begin{center}
    $\{-2^2,-3^2,..,-(q-1)^2\} = p-1$.
\end{center}
Thus, all sets are disjoint. Therefore, the complete set of numbers that are primitive roots modulo are $-2^2,-3^2,...,-q^2$. 
\end{proof}

\subsection*{7.30 Exercise} 
\quad \textit{Verify that the primitive roots modulo 23 that we listed earlier in this section are in fact the same as those given by Miller's Theorem.}

\begin{itemize}
    \item $1^2 \equiv 22^2 \equiv 1 \;(\bmod\; 23)$
    \item $2^2 \equiv 21^2 \equiv 4 \;(\bmod\; 23)$
    \item $3^2 \equiv 20^2 \equiv 9 \;(\bmod\; 23)$
    \item $4^2 \equiv 19^2 \equiv 16 \;(\bmod\; 23)$
    \item $5^2 \equiv 18^2 \equiv 2 \;(\bmod\; 23)$
    \item $6^2 \equiv 17^2 \equiv 13 \;(\bmod\; 23)$
    \item $7^2 \equiv 16^2 \equiv 3 \;(\bmod\; 23)$
    \item $8^2 \equiv 15^2 \equiv 18 \;(\bmod\; 23)$
    \item $9^2 \equiv 14^2 \equiv 12 \;(\bmod\; 23)$
    \item $10^2 \equiv 13^2 \equiv 8 \;(\bmod\; 23)$
    \item $11^2 \equiv 12^2 \equiv 6 \;(\bmod\; 23)$
\end{itemize}
Thus the set of quadratic residue modulo 23 is $\{1,4,9,16,2,13,3,18,12,8,6\}$

\subsection*{7.31 Exercise} 
\quad \textit{List the primitive roots and quadratic residues modulo 47.}
\begin{itemize}
    \item $1^2 \equiv 46^2 \equiv 1 \;(\bmod\; 47)$
    \item $2^2 \equiv 45^2 \equiv 4 \;(\bmod\; 47)$
    \item $3^2 \equiv 44^2 \equiv 9 \;(\bmod\; 47)$
    \item $4^2 \equiv 43^2 \equiv 16 \;(\bmod\; 47)$
    \item $5^2 \equiv 42^2 \equiv 25 \;(\bmod\; 47)$
    \item $6^2 \equiv 41^2 \equiv 36 \;(\bmod\; 47)$
    \item $7^2 \equiv 40^2 \equiv 2 \;(\bmod\; 47)$
    \item $8^2 \equiv 39^2 \equiv 17 \;(\bmod\; 47)$
    \item $9^2 \equiv 38^2 \equiv 34 \;(\bmod\; 47)$
    \item $10^2 \equiv 37^2 \equiv 6 \;(\bmod\; 47)$
    \item $11^2 \equiv 36^2 \equiv 27\;(\bmod\; 47)$
    \item $12^2 \equiv 35^2 \equiv 3 \;(\bmod\; 47)$
    \item $13^2 \equiv 34^2 \equiv 28 \;(\bmod\; 47)$
    \item $14^2 \equiv 33^2 \equiv 8 \;(\bmod\; 47)$
    \item $15^2 \equiv 32^2 \equiv 37 \;(\bmod\; 47)$
    \item $16^2 \equiv 31^2 \equiv 21 \;(\bmod\; 47)$
    \item $17^2 \equiv 30^2 \equiv 7 \;(\bmod\; 47)$
    \item $18^2 \equiv 29^2 \equiv 42 \;(\bmod\; 47)$
    \item $19^2 \equiv 28^2 \equiv 32 \;(\bmod\; 47)$
    \item $20^2 \equiv 27^2 \equiv 24 \;(\bmod\; 47)$
    \item $21^2 \equiv 26^2 \equiv 18 \;(\bmod\; 47)$
    \item $22^2 \equiv 25^2 \equiv 14 \;(\bmod\; 47)$
    \item $23^2 \equiv 24^2 \equiv 12 \;(\bmod\; 47)$
\end{itemize}
Thus the set of quadratic residue modulo 23 is
\begin{center}
    $\{1,4,9,16,25,36,2,17,34,6,27,3,28,8,37,21,7,42,32,24,18,14,12\}$
\end{center}

\subsection*{7.32 Blank Paper Exercise} 
\begin{itemize}
    \item Quadratic Congruences
    \item Quadratic Residues
    \item Legendre Symbol
    \item Euler's Criterion
    \item Gauss' Lemma
    \item Quadratic Reciprocity
    \item Sophie Germain
\end{itemize}

\section*{Diagramming Numbers Modulo a Prime}

\subsection*{7.1.1 Exercise} 
\quad \textit{Construct squaring diagrams similar to that of Figure 7.1 for all primes up to p = 31 by hand.}

\subsection*{7.1.2 Theorem} 
\quad \textit{Let p be prime. For $0 \leq a \leq p$, the only solutions to the congruence $a^2 \equiv 0 \;(\bmod\; p)$ are $a=0$ and $a=p$.}

\begin{proof}
Let p be prime. For $0 \leq a \leq p$, the only solutions to the congruence $a^2 \equiv 0 \;(\bmod\; p)$ are $a=0$ and $a=p$. Since $p \nmid a$ when $0 \leq a \leq p$.
\end{proof}

\subsection*{7.1.3 Theorem} 
\quad \textit{Let p be an odd prime and let $a,b$ be integers, $1 \leq a < b < p$, such that $a^2 \equiv b^2 \;(\bmod\; p)$. Then $a+b = p$.}

\begin{proof}
Let p be an odd prime and let $a,b$ be integers, $1 \leq a < b < p$, such that $a^2 \equiv b^2 \;(\bmod\; p)$. Then by direct proof,
\begin{align*}
    &&a^2 &\equiv b^2 \;(\bmod\; p) &&\\
    &&a &\equiv b \;(\bmod\; p) &&\\
    &&a + b &\equiv 0 \;(\bmod\; p) &&
\end{align*}
Then, $p\mid a+b \Longrightarrow a+b = kp, \exists k \in \mathbf{Z}$. Thus, $a+b = p$.
\end{proof}

\subsection*{7.1.4 Exercise} 
\quad \textit{Denote the tree rooted at 1 in the squaring diagram as $T_1$.}

\subsection*{7.1.5 Theorem} 
\quad \textit{Let $p= 2^km+1$, with m an odd prime.}

\begin{proof}
Suppose prime p such that $p= 2^km+1$, with m an even prime. Then,
\begin{align*}
    &&p &= 2^k(2)+1&&\\
    &&p &= 2^{k+1}+1&&
\end{align*}
Now by Fermat's Little Theorem,
\begin{align*}
    &&a^{p-1} &\equiv 1 \;(\bmod\; p)&&\\
    &&a^{2^k} &\equiv 1^{0.5} \;(\bmod\; p)&&\\
    &&a^{2^k} &\equiv 1 \;(\bmod\; p)&&
\end{align*}
Thus, m must be odd.
\end{proof}

\subsection*{7.1.6 Theorem} 
\quad \textit{If p is a Fermat prime, the squaring diagram for p consists of the single binary tree $T_1$.}

\subsection*{7.1.7 Theorem} 
\quad \textit{Let $p= 2^km+1$ be prime.}

\subsection*{7.1.8 Question} 
\quad \textit{For p prime, can you make a conjecture about cycle periods in the squaring diagram?}

\subsection*{7.1.9 Question} 
\quad \textit{What conjecture can you make about the relation of the squaring diagram for a prime p and for the composite number 2p?}

\end{document}