Skip to main content
Logo image

Exercises 16.8 Exercises


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


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.


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


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?


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

Exercise Group.

Solve the following congruences without using a computer.


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


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


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


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


Show that a quadratic residue can’t be a primitive root if \(p>2\text{.}\)


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


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


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.


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


Show that, given a power of two, \(2^e\text{,}\) greater than four, \(x^2\equiv a\) (mod \(2^e\)) either has zero or four solutions. (Remark 7.2.7 or even Exercise 7.7.15 may be useful here.)


Let \(n=pq\) for odd primes \(p,q\text{.}\) Create a quadratic \(ax^2+bx+c\) for which \(\gcd(2a,n)=p > 1\) (and reduces to a solvable linear congruence modulo \(p\)) and which is a (solvable) quadratic modulo \(q\text{,}\) for which the quadratic also has solutions modulo \(n\text{.}\) (Hint: Try small \(p,q\) and \(a=p\text{.}\))