Exercises 16.8 Exercises
1.
Fill in all the details of Example 16.0.2 for the congruences x^2+5x+5\equiv 0\text{ (mod }5) and x^2+5x+7\equiv 0\text{ (mod }n)\text{.}
2.
Prove that if e>1\text{,} then there is no solution to
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.
8.
Prove that if p is an odd prime
9.
Explore and conjecture a formula for
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{:}
(A harder problem is to prove your evaluation works for all p\text{.})