NTIC Exercises

Exercises 16.8 Exercises

1.

Fill in all the details of Example 16.0.2 for the congruences $x^{2} + 5 x + 5 \equiv 0 (mod 5)$ and $x^{2} + 5 x + 7 \equiv 0 (mod n) .$

🔗

2.

Prove that if $e > 1,$ then there is no solution to

x^{2} \equiv - 1 (mod 2^{e}) .

Use our knowledge of squares modulo 4.

🔗

3.

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.)

🔗

4.

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. Why is this exercise not as challenging as it seems, and what would you do to make it harder?

🔗

5.

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

🔗

Solve the following congruences without using a computer.

🔗

6.

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

🔗

7.

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

🔗

8.

Prove that if $p$ is an odd prime

\sum_{a = 1}^{p - 1} (\frac{a}{p}) = 0 .

🔗

9.

Explore and conjecture a formula for

\sum_{a \in Q_{p}} a,

possibly dependent upon some congruence class for $p .$

🔗

10.

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

🔗

11.

Show that if $p$ is an odd prime, then there are exactly $\frac{p - 1}{2} - ϕ (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,$ 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 (mod 12) .$ (See Proposition 17.3.4 for full details of $(\frac{3}{p}) .$ )

🔗

16.

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 :$

\sum_{a = 1}^{p - 2} (\frac{a}{p}) (\frac{a + 1}{p})

(A harder problem is to prove your evaluation works for all $p .$ )