\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath}
\def\qr#1/#2 {\ensuremath{\left(\frac{#1}{#2}\right)}}
\begin{document}

\noindent Geoffrey Thomas \\
\noindent 18.781 pset 6 \\
\noindent Collaborators: Liz Denys

\begin{enumerate}
\item[3-2 6.] Yes, because \[\qr150/1009 = \qr25/1009 \qr6/1009 = 1 \cdot \qr2/1009 \qr3/1009 = (-1)^{((1008+1)^2-1)/8} \qr1009/3 = 1 \cdot 1 = 1\]
\item[3-2 7.] First, 13 is a quadratic residue of 2. Then considering odd primes, 13 is of the form $4k+1$, so $x^2 \equiv 13 \pmod p$ has a solution when $x^2 \equiv p \pmod 13$ does. The only odd prime that is a quadratic residue of 13 is 3.
\item[3-2 8.] 2 is clearly inadmissible. Therefore, $\qr 10/p = \qr 5/p \qr 2/p = \qr p/5 (-1)^{(p^2-1)/8}$. 
\item[3-2 9.] 2 is inadmissible. For all other primes, $\qr 5/q = \qr q/5 $, so any prime congruent to a quadratic nonresidiue modulo 5, specifically any prime ccongruent to 2 or 3 modulo 5, satisfies this equation.
\item[3-2 13.]
\item[3-2 16.] Since the order of any residue divides $2^{2^n}$, any non-primitive root is also a quadratic residue. Therefore we can determine whether 3 is a primitive root simply by calculating \qr 3/p , which is $1$ if $n=1$ and \qr p/3 for $n>1$. In the latter case, $p-1$ is a square and is therefore congruent to a quadratic residue modulo 3, the only one of which is $1$. So $p \equiv 2 \pmod{3}$, which is not a quadratic residue, so 3 is a primitive root.
\item[3-2 20.]

\item[3-3 3.] $\qr 11/61 = \qr 61/11 = \qr 5/11 = \qr 11/5 = \qr 1/5 = 1$.

$\qr 42/97 = \qr 2/97 \qr 21/97 = (-1)^{(97^2-1)/8} \qr 97/21 = 1 \cdot \qr 13/21 = -1$.

$\qr -43/97 =  \qr 43/79 = \qr 79/43 = -\qr 7/43 = \qr 43/7 = \qr 1/7 = 1$.

$\qr 31/103 = -\qr 103/31 = -\qr 10/31 = -1$.

\item[3-3 5.] These are Legendre symbols for $p$ n odd prime, so we can therefore analyze the sum by noting that half of the residues are quadratic, and so the 1s and -1s cancel yielding 0.
\item[3-3 13.] 
\item[3-3 14.] $\qr a/p = \qr p/a $. We know that $x=b$ satisfies $x^2 \equiv p \pmod{a}$, so the Jacobi symbol is 1.
\item[3-3 17.] $s(0, p) = \sum_{n=1}^p \qr n^2/p = \sum_{n=1}^{p-1} 1 + 0 = p-1$.

$\sum_{a=1}^p \sum_{n=1}^p \qr n(n+a)/p $, by part 5 of theorem 3.6, is equivalent to $\sum_{a=1}^p \sum_{n=1}^p \qr na/p = \sum_{a=1}^p \sum_{n=1}^p \qr n/p \qr a/p $. There are $(p-1)/2$ quadratic residues modulo p and as many nonresidues, and one residue equivalent to zero. Therefore, of this summation of $p^2$ terms, $(p-1)^2/2$ of the terms have both Jacobi symbols evaluate the same nonzero value and therefore equal 1, as many have different nonzero values and equal -1, and the remaining $2p-1$ terms are zero. So the sum is zero.


\item[3-3 20.]

\begin{verbatim}
x^2 - n^2 = a mod p
(x+n)(x-n) = a mod p
u(u-2n) = a mod p
\end{verbatim}

\item[3-4 1.] positive definite, negative definite, indefinite, positive definite, indefinite, positive definite
\item[3-4 4.] $(3+2\sqrt{2})^k = \sum_{i=0}^{[k/2]} \binom{k}{2i} 9^{k-i} 8^i + \sum_{i=0}^{[(k-1)/2]} \binom{k}{2i+1} 9^{k-i} 8^i \cdot 6 \sqrt{2}$, by splitting odd and even indices from the original binomial expansion. To expand $(3-2\sqrt{2})$, we need only negate the odd-indexed terms, which yields $x_k - y_k\sqrt{2}$.

\begin{align*}
\left(3+2\sqrt{2}\right)^k \left(3-2\sqrt{2}\right)^k &= \left(x_k + y_k \sqrt{2}\right)\left(x_k - y_k \sqrt{2}\right) \\
\left(9 - 8\right)^k &= x_k^2 - 2y_k^2
\end{align*}

so $x_k^2 - 2y_k^2 = 1$ for all positive $k$.

\begin{align*}
\left(3+2\sqrt{2}\right)^{k+1} &= \left(3+2\sqrt{2}\right)^k\left(3+2\sqrt{2}\right) \\
x_{k+1} + y_{k+1}\sqrt{2} &= \left(x_k + y_k\sqrt{2}\right)\left(3+2\sqrt{2}\right) \\
&= 3 x_k + 4 y_k + \left(2 x_k + 3 y_k\right)\sqrt{2}
\end{align*}

We can demonstrate $(x_k, y_k) = 1$ by induction. This is true of the base case $k=1$; then at each step $(x_{k+1}, y_{k+1}) = (3x_k+4y_k, 2x_k+3y_k) = (x_k, y_k) = 1$. In addition, since the recursive formula only includes a summation of previous terms and the initial terms are positive, both sequences are strictly increasing. Therefore for any $k$ we can generate a unique pair $x_k, y_k$ such that $x_k^2 - 2y_k^2 = 1$.

\item[3-4 7.] The solutions to a quadratic equation are $$\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$ both roots of which are rational iff $\sqrt{b^2-4ac}$ is rational, i.e., if the discriminant. It is not possible for one root to be rational and the other not.

\item[4.]
\begin{align*}
& \left(x_1^2 + dy_1^2\right)\left(x_2^2 + dy_2^2\right) \\
= & x_1^2 x_2^2 + d x_1^2 y_2^2 + d x_2^2 y_1^2 + d^2 y_1^2 y_2^2 \\
= & \left(x_1 x_2 + d y_1 y_2\right)^2 + d\left(x_1 y_2 - y_1 x_2\right)^2
\end{align*}

\end{enumerate}
\end{document}