NTIC Exercises

🔗

Exercises 16.8 Exercises

🔗

1.

Fill in all the details of Example 16.0.2.

🔗

2.

Prove that if $e>1\text{,}$ then there is no solution to

$\begin{equation*} x^2\equiv -1\text{ (mod }2^e)\text{.} \end{equation*}$

Use our knowledge of squares modulo 4.

🔗

3.

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

🔗

4.

Clearly $4$ has a square root modulo $7\text{.}$ Find all square roots of $4$ modulo $7^3$ without using Sage or trying all $343$ possibilities. Why is this exercise not as challenging as it seems, and what would you do to make it harder?

🔗

5.

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

🔗

Solve the following congruences without using a computer.

🔗

6.

$x^2+6x+5\equiv 0$ (mod $17$ )

🔗

7.

$5x^2+3x+1\equiv 0$ (mod $17$ )

🔗

8.

Prove that if $p$ is an odd prime

$\begin{equation*} \sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\text{.} \end{equation*}$

🔗

9.

Explore and conjecture a formula for

$\begin{equation*} \sum_{a\in Q_p} a\text{,} \end{equation*}$

possibly dependent upon some congruence class for $p\text{.}$

🔗

10.

Show that a quadratic residue can't be a primitive root if $p>2\text{.}$

🔗

11.

Show that if $p$ is an odd prime, then there are exactly $\frac{p-1}{2}-\phi(p-1)$ residues which are neither QRs nor primitive roots. (Hint: don't think too hard – just do the obvious counting up.)

🔗

12.

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

🔗

13.

Evaluate Legendre symbols for all $a\neq 0$ where $p=7\text{,}$ using Euler's Criterion.

🔗

14.

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.

🔗

15.

Use Euler's Criterion and the ideas of Proof 16.7.1 to prove that $3$ has a square root modulo $p$ if $p\equiv 1\text{ (mod }12)\text{.}$ (See Proposition 17.3.4 for full details of $\left(\frac{3}{p}\right)\text{.}$ )

🔗

16.

Explore for a pattern for, given $p\text{,}$ 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\text{:}$

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