\documentclass[12pt]{article}

\usepackage[table]{xcolor}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{hyperref}
\usepackage{authblk}
\usepackage[all]{xy}
\usepackage{enumitem}
\usepackage{stmaryrd}
\usepackage[makeroom]{cancel}
\usepackage{bbm}
\usepackage{fancyvrb}
\usepackage{xstring} % For the replace command
\usepackage{tikz}
%\usetikzlibrary{intersections}
\usepackage{xcolor,cancel}

\newcommand\hcancel[2][black]{\setbox0=\hbox{$#2$}%
\rlap{\raisebox{.45\ht0}{\textcolor{#1}{\rule{\wd0}{1pt}}}}#2} 

\usepackage[normalem]{ulem}

\usepackage{xsim}

\xsimsetup{solution/print=true} %%%%%%

\usepackage{xeCJK}

\newtheorem*{rk}{Remark}


\usepackage{xlop}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\f}{\mathfrak{f}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\K}{\mathbb{K}}
\renewcommand{\l}{\mathfrak{l}}
\newcommand{\p}{\mathfrak{p}}
\renewcommand{\P}{\mathfrak{P}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\lcm}{\operatorname{lcm}}

\topmargin -2.5cm
\textheight 25cm
\textwidth 15cm


\begin{document}

\begin{center}

{\Huge Introduction to number theory \\ Exercise sheet 3}

\vspace{0.5cm}

\url{https://www.maths.tcd.ie/~mascotn/teaching/2021/MAU22301/index.html}

\vspace{0.5cm}

Version: \today

\vspace{1cm}

Email your answers to \href{mailto:makindeo@tcd.ie}{makindeo@tcd.ie} by Friday November 5th, 2PM.

The use of electronic calculators and computer algebra software is allowed.

\end{center}

\vspace{1cm}

\begin{exercise}[subtitle=P\'epin's test (100 pts)]
Recall (cf Exercise 12 of Sheet 1) that the $n$-th Fermat number is $F_n = 2^{2^n}+1$, where $n \in \N$.

\emph{In this definition, as usual, $a^{b^c}$ means $a^{(b^c)}$ rather than $(a^b)^c$ (since the latter simplifies into $a^{(b \times c)}$).}

\begin{enumerate}
\item (10 pts) Prove that $F_n \equiv -1 \pmod 3$.

\item (50 pts) Prove that if $F_n$ is prime, then $3^{(F_n-1)/2} \equiv -1 \pmod{F_n}$. \linebreak
\emph{Hint: What is this question doing in the middle of an assignment on the Legendre symbol?}

\item (40 pts) Conversely, prove that if $3^{(F_n-1)/2} \equiv -1 \pmod{F_n}$, then $F_n$ is prime. \linebreak
\emph{Hint: What can you say about the multiplicative order of $3 \bmod F_n$?}

\end{enumerate}

\emph{Remark: This primality test, named after the 19th century French mathematician Th\'eophile P\'epin, only applies to Fermat numbers, but is much faster than the general-purpose tests that can deal with any integer. It was used in 1999 to prove that $F_{24}$ is composite, which is quite an impressive feat since $F_{24}$ has 5050446 digits!}
\end{exercise}
\begin{solution}
\begin{enumerate}
\item Since $2 \equiv -1 \pmod 3$, we have \[F_n = 2^{2^n}+1 \equiv (-1)^{2^n}+1 = 1+1=2 \equiv -1 \pmod 3\] as $n \geqslant 1$.

\item If $F_n=p$ is prime, then we have $3^{(F_n-1)/2} = 3^{p'} \equiv \left( \frac{3}{p} \right) \pmod{p}$, and $\left( \frac{3}{p} \right) = \left( \frac{p}{3} \right)$ by quadratic reciprocity since clearly $p=F_n \equiv 1 \pmod 4$. Finally, by the previous question $\left( \frac{p}{3} \right) = \left( \frac{-1}{3} \right) = -1$, whence the result.

\item If $3^{(F_n-1)/2} \equiv -1 \pmod{F_n}$, then $3^{F_n-1} \equiv (-1)^2=1 \pmod{F_n}$, so the multiplicative order of $3 \bmod F_n$ divides $F_n-1=2^{2^n}$, which is a power of $2$. Since $3^{(F_n-1)/2} \equiv -1 \not \equiv 1 \pmod{F_n}$, and since 2 is the only prime dividing $F_n-1$, this order is in fact exactly $F_n-1$. So the powers of 3 give us $F_n-1$ elements in $(\Z/F_n \Z)^\times$. But the number of elements in  $(\Z/F_n \Z)^\times$ is at most $F_n-1$ since 0 is not invertible, so the powers of 3 give us all of $(\Z/F_n \Z)^\times$ (i.e. 3 is a primitive root mod $F_n$) and all nonzero elements in $\Z/F_n \Z$ are invertible. This means that $\Z/F_n \Z$ is a field, which implies that $F_n$ is prime.
\end{enumerate}
\end{solution}

\bigskip

\bigskip

\textbf{This was the only mandatory exercise, that you must submit before the deadline. The following exercises are not mandatory; they are not worth any points, and you do not have to submit them. However, I highly recommend that you try to solve them for practice, and you are welcome to \href{mailto:mascotn@tcd.ie}{email me} if you have questions about them. The solutions will be made available with the solution to the mandatory exercise.}

\bigskip

\begin{exercise}[subtitle=Legendre symbols]
Evaluate the following Legendre symbols:

\begin{enumerate}
\item $\displaystyle \left( \frac{10}{1009} \right)$,
\item $\displaystyle \left( \frac{261}{2017} \right)$,
\item $\displaystyle \left( \frac{-77}{9907} \right)$,
\item $\displaystyle \left( \frac{-6}{10007} \right)$,
\item $\displaystyle \left( \frac{261}{2903} \right)$,
\item $\displaystyle \left( \frac{8000}{29} \right)$.
\end{enumerate}

\emph{Note: 1009, 2017, 9907, 10007, 2903, and 29 are prime.}
\end{exercise}

\begin{solution}
\begin{enumerate}
\item $\displaystyle \left( \frac{10}{1009} \right) = \left( \frac{2}{1009} \right) \left( \frac{5}{1009} \right) = +1 \times + \left( \frac{1009}{5} \right)$

since $1009 \equiv 1 \pmod 8$ and 1009 (or 5) $\equiv +1 \pmod 4$

$\displaystyle =\left( \frac{9}{5} \right)=+1$

since $1009 \equiv 9 \pmod 5$ and $9=3^2$ is obviously a square mod 5.

\item $\displaystyle \left( \frac{261}{2017} \right) =  \left( \frac{3^2}{2017} \right)  \left( \frac{29}{2017} \right) =  +1 \times +\left( \frac{2017}{29} \right)$

since $3^2$ is obviously a square and since 2017 (or 29) $\equiv +1 \pmod 4$ 

$\displaystyle = \left( \frac{16}{29} \right) = +1$

since $2017 \equiv 16=4^2 \pmod {29}$.

\item $\displaystyle \left( \frac{-253}{9923} \right) =  \left( \frac{-1}{9923} \right)  \left( \frac{11}{9923} \right)  \left( \frac{23}{9923} \right)= -1 \times - \left( \frac{9923}{11} \right) \times - \left( \frac{9923}{23} \right)$ 

since $253 = 11 \times 23$ and 9923, 11 and 23 are all $\equiv -1 \pmod 4$ 

$\displaystyle = -\left( \frac{1}{11} \right) \left( \frac{11 \times 30^2}{23} \right)$

since $9923 \equiv 1 \pmod {11}$ and $9923 \equiv 9900 = 11 \times 30^2 \pmod{23}$

$\displaystyle = -  \left( \frac{11}{23} \right) = -- \left( \frac{23}{11} \right)$

since 11 and 23 are both $\equiv -1 \pmod 4$

$\displaystyle = \left( \frac{1}{11} \right) = +1$.

\item $\displaystyle \left( \frac{-6}{10007} \right) =\left( \frac{-1}{10007} \right)  \left( \frac{2}{10007} \right) \left( \frac{3}{10007} \right) = -1 \times +1 \times - \left( \frac{10007}{3} \right)$

since $10007 \equiv -1 \pmod 4$, $10007 \equiv -1 \pmod 8$ and $3'$ and $10007'$ are both odd (because $3$ and $10007 \equiv -1 \pmod 4$)

$\displaystyle =+\left( \frac{-1}{3} \right)=-1$

since $10007 \equiv 8 \equiv -1 \pmod 3$ (sum of digits) and $3 \equiv -1 \pmod 4$.

\item $\displaystyle \left( \frac{261}{2903} \right) =  \left( \frac{3^2}{2903} \right)  \left( \frac{29}{2903} \right) =  +1 \times +\left( \frac{2903}{29} \right)$

since $3^2$ is obviously a square (mod 2903 and even in $\Z$) and since $29'$ is even as $29 \equiv +1 \pmod 4$ 

$\displaystyle = \left( \frac{3}{29} \right) = + \left( \frac{29}{3} \right)$

as $2903 \equiv 3\pmod{29}$ and again because $29'$ is even

$\displaystyle = \left( \frac{-1}{3} \right) = -1$

as above.

\item We could start by reducing $8000$ mod $29$ and proceed as usual, but there is a much easier way:

$\displaystyle \left( \frac{8000}{29} \right) =  \left( \frac{2^6 5^3}{29} \right) = \left( \frac{2^6 5^2}{29} \right)  \left( \frac{5}{29} \right) = \left( \frac{5}{29} \right)$

since $2^6 5^2 = (2^3 5)^2$ is obviously a square mod 29

$\displaystyle  = + \left( \frac{29}{5} \right)  = \left( \frac{-1}{5} \right)  = +1$

since $5'$ (and also $29'$) is even and since $29 \equiv -1 \pmod{5}$ and since $5 \equiv +1 \pmod 4$.
\end{enumerate}
\end{solution}

\bigskip

\begin{exercise}[subtitle=Applications of $( \frac{-3}p )$]
\begin{enumerate}
\item Let $p > 3$ be a prime. Prove that $-3$ is a square mod $p$ if and only if $p \equiv 1 \pmod 6$.

\item An element $x \in \Z/p\Z$ is called a \emph{cube root of unity} if it satisfies $x^3 =1$. Use the previous question and the identity $x^3-1=(x-1)(x^2-x+1)$ to compute the number of cube roots of unity in $\Z/p\Z$ in terms of $p \bmod 6$. 

\item Find another way to compute the number of cube roots of unity in $\Z/p\Z$ in terms of $p \bmod 6$ by considering the map
\[ \begin{array}{ccc} (\Z/p\Z)^\times & \longrightarrow & (\Z/p\Z)^\times \\ x & \longmapsto & x^3. \end{array}\]

\item Use question 1. of this exercise to prove that there are infinitely many primes $p$ such that $p \equiv 1 \pmod 6$.

\emph{Hint: Suppose on the contrary that there are finitely many, say $p_1, \cdots, p_k$, and consider $N=12 (p_1 \cdots p_k)^2+1$.}
\end{enumerate}

\end{exercise}

\begin{solution}
\begin{enumerate}
\item We compute that
\[ \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{3}{p} \right) = (-1)^{p'} (-1)^{\frac{3-1}2 p'} \left( \frac{p}{3} \right) = \left( \frac{p}{3} \right). \]

Besides, as $p >3$, we know that $p \equiv \pm 1 \pmod 6$. So if $p \equiv +1 \pmod 6$, then $p \equiv +1 \pmod 3$, so $\left( \frac{p}{3} \right) = \left( \frac{1}{3} \right) = +1$, but if $p \equiv -1 \pmod 6$, then $p \equiv -1 \pmod 3$, so $\left( \frac{p}{3} \right) = \left( \frac{-1}{3} \right) = -1$ since $3 \equiv -1 \pmod 4$.

\item Cubic roots of unity are by definition the same as the roots of the polynomial $x^3-1=(x-1)(x^2-x+1)$. The factor $x-1$ gives the obvious root $x=1$. Also, the discriminant of $x^2-x+1$ is $\Delta=-3$, so by the previous question this factor has 2 distinct roots when $p \equiv +1 \pmod 6$, and 0 roots when $p \equiv -1 \pmod 6$. Besides, these roots can never be $x=1$, since $x^2-x+1$ assumes the value 1 at $x=1$, and $1 \neq 0$ in $\Z/p\Z$ for all $p$.

Thus the number of cubic roots of unity in $\Z/p\Z$ is $1+2=3$ when $p \equiv +1 \pmod 6$, and $1+0=1$ when $p \equiv -1 \pmod 6$.

\item If $p \equiv +1 \pmod 6$, then $6 \mid (p-1)$, so $\gcd(3,p-1)=3$, which means that the map
\[ \begin{array}{ccc} (\Z/p\Z)^\times & \longrightarrow & (\Z/p\Z)^\times \\ x & \longmapsto & x^3 \end{array}\]
is 3-to-1. Since $1$ is clearly in its image (it is reached by $x=1$), it is reached by exactly 3 values of $x$; in other words, there are 3 cubic roots of unity.

On the other hand, if $p \equiv -1 \pmod 6$, then $\gcd(3,p-1)=1$, so the map
\[ \begin{array}{ccc} (\Z/p\Z)^\times & \longrightarrow & (\Z/p\Z)^\times \\ x & \longmapsto & x^3 \end{array}\]
is 1-to-1, so it assumes the value 1 exactly once, so there is 1 cubic root of unity.

\item Let us suppose that $p_1, \cdots, p_k$ are all the primes $\equiv +1 \pmod 6$, let $N=12 (p_1 \cdots p_k)^2+1$, and let $p$ be a prime dividing $N$ (which exists since obviously $N>1$). Then $p$ cannot be 2, nor 3, nor any of the $p_1, \cdots, p_k$, for else it would divide 1. So we must have $p \equiv -1 \pmod 6$. But since $p \mid N$, we have $-1 \equiv 12 (p_1 \cdots p_k)^2 \pmod p$, so $-3 \equiv 36 (p_1 \cdots p_k)^2 = (6p_1 \cdots p_k)^2$ is a square mod $p$, which contradicts question 1.
\end{enumerate}
\end{solution}

\bigskip

\begin{exercise}[subtitle=A quadratic equation mod 2021 (100pts)]
Determine the number of solutions to the equation
\[ x^2-3x+7=0, \]
and then to
\[ x^2-3x+9=0, \]
\begin{enumerate}
\item (30pts) in $\Z/43\Z$,
\item (30pts) in $\Z/47\Z$,
\item (40 pts) in $\Z/2021\Z$ (\emph{Hint: 與上次作業相同的提示}).
\end{enumerate}
\emph{You may freely use the fact that $2021=43\times47$ and that $43$ and $47$ are prime.}
\end{exercise}
\begin{solution}
\begin{enumerate}
\item The discriminant of the first equation is
\[ \Delta_1 = (-3)^2-4\times7 = -19. \]
We compute that 
\[ \left( \frac{\Delta_1}{43} \right) = \left( \frac{-1}{43} \right) \left( \frac{19}{43} \right) = (-1)^{43'} (-1)^{19' 43'} \left( \frac{43}{19} \right) = -- \left( \frac{43}{19} \right) \]
since $43'=21$ and $19'=9$ are both odd
\[ = \left( \frac{5}{19} \right) = (-1)^{5'19'} \left( \frac{19}{5} \right) = \left( \frac{4}{5} \right) = +1 \]
since $43 \equiv 5 \bmod 19$, $5'=2$ is even, and $19 \equiv 4 = 2^2 \bmod 5$. Therefore, the first equation has two solutions in $\Z/43\Z$.

For the second equation, we have
\[ \Delta_2 = (-3)^2-4\times 6 = -27, \]
and similarly we find
\[ \left( \frac{-27}{43} \right) = \left( \frac{-1}{43} \right) \left( \frac{3}{43} \right) \cancel{\left( \frac{3^2}{43} \right)} = (-1)^{43'} (-1)^{3' 43'} \left( \frac{43}{3} \right) =  \left( \frac{43}{3} \right) = \left( \frac{1}{3} \right) = +1 \]
since $43'$ and $3'=1$ are both odd, so the second equation also has two solutions in $\Z/43\Z$.

\item The discriminants are still the same of course, but this time we must compute their Legendre symbol with $p=47$.

We find that
\[ \left( \frac{\Delta_1}{47} \right) = \left( \frac{-1}{47} \right) \left( \frac{19}{47} \right) = (-1)^{47'} (-1)^{19' 47'} \left( \frac{47}{19} \right) = -- \left( \frac{47}{19} \right) = \left( \frac{9}{19} \right) = +1 \]
since $47'=23$ and $19'=9$ are both odd and $47 \equiv 9=3^3 \bmod 19$, so the first equation has two solutions in $\Z/47\Z$; and
\[ \left( \frac{-27}{47} \right) = \left( \frac{-1}{47} \right) \left( \frac{3}{47} \right) \cancel{\left( \frac{3^2}{47} \right)} = (-1)^{47'} (-1)^{3' 47'} \left( \frac{47}{3} \right) =  \left( \frac{47}{3} \right) \] \[ = \left( \frac{-1}{3} \right) = (-1)^{3'} = -1 \]
(at the last stage, we could also have said that $47 \equiv 2 \bmod 3$, and conclude as $\left( \frac{2}{3} \right) = -1$ as $3 \equiv 3 \bmod 8$), so this time the second equation has no solutions in $\Z/47\Z$.
 
\item We cannot compute Legendre symbols mod $2021$ since $2021$ is not prime.

Instead, we note that since 43 and 47 are distinct primes, they are coprime, so by Chinese remainders we have a 1-to-1 correspondence
\[ \Z/2021\Z \longleftrightarrow \Z/43\Z \times \Z/47\Z, \]
and we claim that for each equation, this restricts to a correspondence
\[ \{ \text{Solutions in }  \Z/2021\Z \} \longleftrightarrow \{ \text{Solutions in } \Z/43\Z \} \times \{ \text{Solutions in }  \Z/47\Z \}. \]
Indeed, it is clear that any solution mod 2021 reduces to a solution mod 43 and to a solution mod 47; and conversely if for example $x \in \Z$  reduces to a solution both mod 43 and mod 47, so that $x^2-3x+7=0$ mod $43$ and mod $47$, then 43 and 47 both divide $x^2-3x+7$, so their product also does since they are coprime.

This shows that solutions mod 2021 are obtained by combining by Chinese remainders a solution mod 43 with a solution mod 47; in particular, the number of solutions mod 2021 is the number of solutions mod 43 times the number of solutions mod 47.

Therefore, the first equation has $2 \times 2 = 4$ solutions in $\Z/2021\Z$ (even though it has degree only 2! This reflects the fact that $\Z/n\Z$ has nasty properties when $n$ is not prime), whereas the second one has $2 \times 0 = 0$ solutions.

For the second equation, we could also have argued that any solution mod 2021 would reduce to a solution mod 47, and we have seen that no such solution exists.
\end{enumerate}
\end{solution}

\bigskip

\begin{exercise}[subtitle=Square roots mod $p$: the easy case]
\begin{enumerate}
\item Let $p$ be a prime such that $p \equiv -1 \pmod 4$, and let $x \in \Z/p\Z$ be such that $\left( \frac{x}p \right)=+1$. Prove that $y=x^{\frac{p+1}4}$ is a square root of $x$, that is to say that $y^2=x$.

\item What happens if $\left( \frac{x}p \right)=-1$? What if $p \not \equiv -1 \pmod 4$?
\item (Application) Use question 1. to find explicitly the solutions to the equations of the previous Exercise in $\Z/43\Z$ and $\Z/47\Z$.
\end{enumerate}
\end{exercise}

\begin{solution}
\begin{enumerate}
\item We have $y^2 = x^{\frac{p+1}2} = x^{\frac{p-1}2} x = x$ since $x^{\frac{p-1}2} = \left( \frac{x}p \right)=+1$ in $\Z/p\Z$.

\item If $\left( \frac{x}p \right)=-1$, the same computation shows that $y^2=-x$ instead of $x$.

\emph{Remark: $\left( \frac{-x}p \right)=\left( \frac{-1}p \right)\left( \frac{x}p \right)=-\left( \frac{x}p \right)$ when $p \equiv -1 \pmod 4$, so exactly one of $x$ and $-x$ is a square, and $y$ is then a square root of that one.}

If $p \equiv +1 \pmod 4$, then $\frac{p+1}4 \not \in \Z$ so the formula $y=x^{\frac{p+1}4}$ is meaningless (and therefore useless).

\item We see that 43 and 47 are both $-1$ mod 4, so we may apply the formula found in question 1.

 Mod 43, we get
\[ (-19)^{\frac{43+1}4} = (-19)^{11} = - 19^{11} = - 19^8 19^2 19 = - {{19^2}^2}^2 19^2 19 = 14 \bmod 43, \]
so the solutions to $x^2-3x+7=0$ are $x=(3\pm 14)2^{-1}$. As $2 \times 22 = 43+1$, we have $2^{-1} = 22 \bmod 43$, so these solutions are $x=-13=30$ and $x=16$.

Similarly, we find $(-27)^{11} = 4 \bmod 43$ (cleverer: write $\sqrt{-27}=\sqrt{-3^3} = 3 \sqrt{-3}$, and work with $-3$ instead of $-27$), so the solutions to the second equation are $x=(3 \pm 4) \times 22 \bmod 43$, namely $21$ and $25=-18$.

Finally, mod 47 we have
\[ (-19)^{\frac{47+1}4} = (-19)^12 = {{19^3}^2}^2 = 34 = -13, \]
so the solutions to the first equation in $\Z/47\Z$ are $x=(-3\pm13)/2 = -5$ and~$8$; and we have established that the second equation has no solutions.

Note that if we wanted, we could play Chinese remainders with the solutions $16, 30 \bmod 43$ and $-5,8 \bmod 47$ of the first equation, and find that its four solutions in $\Z/2021\Z$ are 747, $-99$, 102, and $-744$.
\end{enumerate}
\end{solution}

\bigskip

\begin{exercise}[subtitle=Legendre vs. primitive roots]
Let $p \in \N$ be an odd prime, and let $g \in (\Z/p\Z)^\times$ be a primitive root. Prove that $\displaystyle \left( \frac{g}{p} \right) = -1$.
\end{exercise}

\begin{solution}
We know that $\displaystyle \left( \frac{g}{p} \right) \equiv g^{p'} \pmod p$, so the element $g^{p'}$ of $(\Z/p\Z)^\times$ is either 1 or 0 or $-1$. However, it cannot be 0 since $g \neq 0$ and $\Z/p\Z$ is a domain, and it cannot be 1 either since else $g$ would not be a primitive root as $p' < p-1$. So it must be $-1$. Since$p >2$, $0$, 1 and $-1$ are pairwise distinct in $\Z/p\Z$, so it follows that $\displaystyle \left( \frac{g}{p} \right) = -1$.
\end{solution}

\bigskip

\begin{exercise}[subtitle=Sums of Legendre symbols]

Let $p \in \N$ be an odd prime.

\begin{enumerate}
\item Compute $\displaystyle \sum_{x \in \Z/p\Z} \left( \frac{x}{p} \right)$.

\item Compute $\displaystyle \sum_{x \in \Z/p\Z} \left( \frac{x}{p} \right) \left( \frac{x+1}{p} \right)$. 

\emph{Hint: write $x(x+1) = x^2(1+\frac1x)$ wherever legitimate.} 

\end{enumerate}

\end{exercise}
\begin{solution}
\begin{enumerate}
\item In $\Z/p\Z$, we have one zero, $p'$ nonzero squares, and $p'$ nonzero non-squares, so this sum is
\[ 0 + p' - p' = 0. \]

\item We compute
\[  \sum_{x \in \Z/p\Z} \left( \frac{x}{p} \right) \left( \frac{x+1}{p} \right) = \sum_{x \in \Z/p\Z} \left( \frac{x(x+1)}{p} \right) = \sum_{x \in (\Z/p\Z)^\times} \left( \frac{x(x+1)}{p} \right) \]
since the term for $x=0$ is 0
\[ = \sum_{x \in (\Z/p\Z)^\times} \left( \frac{x^2(1+1/x)}{p} \right) = \sum_{x \in (\Z/p\Z)^\times} \left( \frac{1+1/x}{p} \right) = \sum_{x \in (\Z/p\Z)^\times} \left( \frac{1+x}{p} \right) \]
since the map $x \mapsto 1/x$ induces a permutation of $(\Z/p\Z)^\times$
\[ = \sum_{\substack{x \in \Z/p\Z \\ x \neq 1}} \left( \frac{x}{p} \right) = \sum_{x \in \Z/p\Z} \left( \frac{x}{p} \right) - \left( \frac{1}{p} \right) = 0-1 = -1 \]
by the previous question.
\end{enumerate}

\emph{Remark: If we fix $p$ and take $x \in \Z/p\Z$ uniformly at random, the first formula tells us that the expected value of $\left( \frac{x}{p} \right)$ is $0$, and the second one that the covariance of $\left( \frac{x+1}{p} \right)$ and of $\left( \frac{x}{p} \right)$ is $-\frac{1}{p}$. This means that for large $p$, the value of $\left( \frac{x+1}{p} \right)$ is approximately independent of that of $\left( \frac{x}{p} \right)$.}
\end{solution}

\bigskip

\begin{exercise}[subtitle=$\sqrt[67]{2} \bmod 101$]
How many elements $x \in \Z/101\Z$ satisfy $x^{67}=2$? Compute them.

\emph{Note: 101 is prime.}
\end{exercise}

\begin{solution}
Since 67 is coprime to $101-1=100$, the map
\[ \begin{array}{ccc} (\Z/101\Z)^\times & \longrightarrow & (\Z/101\Z)^\times \\ x & \longmapsto & x^{67} \end{array}\]
is 1-to-1. In particular, there is a unique $x$ such that $x^{67}=2$, and it is given by the formula $x=2^{67^{-1}}$, where $67^{-1}$ denotes the inverse of $67 \bmod 100$. We compute that $100=67+33$, and $67=2 \times 33+1$, whence $67 \times 3 - 2\times 100=1$ so $67^{-1}=3$, so the value of this $x$ is
\[ x=2^3=8 \bmod 101. \]
\end{solution}

\bigskip

\begin{exercise}[subtitle=A test for higher powers]

Let $p \in \N$ be a prime, $k \in \N$ be an integer, $g = \gcd(p-1,k)$, and $p_1 = (p-1)/g \in \N$. Finally, let $x \in (\Z/p\Z)^\times$.

\begin{enumerate}
\item Prove that $x$ is a $k$-th power if and only if $x^{p_1}=1 \bmod p$.

\item (Application) Is 2 a cube in $\Z/13\Z$? What about 5?

\item For general $x$, what kind of number is $x^{p_1}$, i.e. which equation does it satisfy?

\item Use the above to define a generalization of the Legendre symbol, and state a couple of its properties.
\end{enumerate}
\end{exercise}

\begin{solution}
\begin{enumerate}
\item Suppose that $x=y^k$ is a $k$-th power. Then we have $x^{p_1} = y^{k p_1} = y^{\frac{k}{g}(p-1)} = 1$ by Fermat's little theorem.

So every $k$-th power is a root of the polynomial $x^{p_1}-1$. This polynomial has degree $p_1$, so it has at most $p_1$ roots; on the other hand, we know that one in $g$ elements of $(\Z/p\Z)^\times$ is a $k$-th power, so there are $(p-1)/g =p_1$ $k$-th powers, all of which are roots of $x^{p_1}-1$ by the above. Thus the roots of $x^{p_1}-1$ are exactly the $k$-th powers, whence the result.

\item We take $p=13$, $k=3$, so $p_1=4$.

We have $2^{p_1} = 16 \equiv 3 \not \equiv 1 \pmod{13}$, so $2$ is not a cube mod $13$, but $5^{p_1} \equiv 1 \pmod{13}$, so $5$ is a cube mod $13$ (and it has $g=3$ cubic roots in $\Z/13 \Z$). 

\item By Fermat's little theorem, we have
\[ 1 = x^{p-1} = x^{p_1 g} = (x^{p_1})^g. \]
So the number $y=x^{p_1}$ always satisfies $y^g=1$; in more pedant terms, it is a $g$-th root of unity.

\item We are thus led to defining $\left( \frac{x}{p} \right)_k = x^{p_1}$.

We have
\[ \left( \frac{x}{p} \right)_k = \left\{ \begin{array}{ll} 0, & \text{ if } x=0, \\ 1, & \text{ if $x$ is a nonzero $k$-th power}, \\ \text{another $g$-th root of unity}, & \text{else.} \end{array} \right. \]

Besides, it follows immediately from the definition that $\left( \frac{xy}{p} \right)_k = \left( \frac{x}{p} \right)_k \left( \frac{y}{p} \right)_k$ for all $x, y \in \Z/p\Z$, and that $\left( \frac{-1}{p} \right)_k = (-1)^{p_1}$.

\emph{Remark: In order to make this generalization of the Legendre symbol really practical, we need a generalization of the quadratic reciprocity law. Such a generalization exists, and is a consequence of the more general \emph{Artin reciprocity law}, which stands at the pinnacle of 20th century number theory, but is unfortunately far beyond the scope of this course.}

\end{enumerate}
\end{solution}

\end{document}
