1

Prove that if \(e>1\), then there is no solution to \begin{equation*}x^2\equiv -1\text{ (mod }2^e)\; .\end{equation*} Use our knowledge of squares modulo 4.

2

For what \(n\) does \(-1\) have a square root modulo \(n\)? (Hint: use prime factorization and the previous problem along with results earlier in the chapter.)

3

Clearly \(4\) has a square root modulo \(7\). Find all square roots of \(4\) modulo \(7^3\) without using Sage or trying all \(343\) possibilities.

4

Solve \(x^2+3x+5\text{ (mod }15)\) using completion of squares and trial and error for square roots.

5

Solve the following congruences without using a computer:

• \(x^2+6x+5\) (mod \(17\))

• \(5x^2+3x+1\) (mod \(17\))

6

Prove that if \(p\) is an odd prime \begin{equation*}\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .\end{equation*}

7

Show that a quadratic residue can't be a primitive root if \(p>2\).

8

Use Euler's Criterion to find all quadratic residues of 13.

9

Use Euler's Criterion to prove that \(2\) has a square root modulo \(p\) if \(p\equiv 1\text{ (mod }8)\).

10

Evaluate all Legendre symbols for \(p=7\) using Euler's Criterion.

11

Explore for a pattern for when \(-5\) is a quadratic residue. Try not to use any fancy criteria, but just to seek a pattern based on the number.

12

Explore for a pattern for, given \(p\), how many pairs of consecutive residues are both actually quadratic residues. Then connect this idea to the following formula, which you should evaluate for the same values of \(p\): \begin{equation*}\sum_{a=1}^{p-2}\left(\frac{a}{p}\right)\left(\frac{a+1}{p}\right)\end{equation*}(A harder problem is to prove your evaluation works for all \(p\).)