Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section17.7Exercises

2

Use the previous problem, your knowledge of \(\left(\frac{-1}{11}\right)\) and of perfect squares to evaluate the other Legendre symbols for \(p=11\).

3

Do any Legendre symbols after Example 17.1.3 which you didn't already do.

4

Make up several hard-looking Legendre symbols \(\left(\frac{a}{29}\right)\) (modulo \(p=29\)) that are easy to solve by adding \(p\) or by factoring \(a\).

5

Use the multiplicative property of the Legendre symbol to give a congruence condition for when \(\left(\frac{-2}{p}\right)=\pm 1\).

6

For \(0<a,b<p\), prove that at least one of \(a,b,\) and \(ab\) is a quadratic residue of \(p\).

7

In Exercise 16.8.6 we proved, for an odd prime \(p\), \begin{equation*}\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .\end{equation*} Conjecture (and, if you can, prove) a similar result for \begin{equation*}\sum_{a\in Q_p} a\, .\end{equation*}

In Example 17.5.3 there are a number of small issues which need proof; here, you have the opportunity to finish them off.

8

Let \(p\) be a prime of the form \(p=2q+1\), where \(q\) is prime (recall that \(q\) is called a Germain prime in this case). Show that every residue from 1 to \(p-2\) is either a primitive root of \(p\) or a quadratic residue. (Hint: Use Euler's Criterion, and ask yourself how many possible orders an element of \(U_p\) can have.)

9

Prove: if \(p\equiv 3\) (mod \(4\)), and if \(a\not\equiv \pm 1,0\), then \(a\) is a QR modulo \(p\) if and only if \(p-a\) is not a QR.

10

Prove that for any prime \(p\), if \(1<i,j<\frac{p}{2}\) and \(i\neq j\), then \(i^2\not\equiv j^2\) (mod \(p\)). (Hint: factor!)

11

Verify the previous exercise for \(p=23\).

12

Prove that if \(\left(\frac{2}{n}\right)\) is the Jacobi symbol instead of the Legendre symbol, it is still true that \(\left(\frac{2}{n}\right)=1\) precisely when \(n\equiv \pm 1\text{ (mod }8)\). (Remember, \(n\) has to be odd by definition.)

13

Compute some Legendre symbols that seem pretty hard by using the Jacobi symbol instead.

14

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

16

Evaluate five non-obvious Legendre symbols \((\frac{a}{p})\) for \(p=47\) using quadratic reciprocity.

17

Find congruence criteria for \(p\) for when \(a\in Q_p\) for \(a=-3,6\), and \(9\). (Hint: Don't do any extra work – use what you know!)

18

Use quadratic reciprocity to prove the surprising statement that \(-5\) is a quadratic residue for exactly those primes for whom the sum of the ones and tens digit is odd. (Did you conjecture this when you completed Exercise 16.8.11? See [C.6.10] about a story behind this unusual result.)

19

Use Sage to explore why repetition in the decimal expansion of \(\frac{a}{p}\) is related to whether \(10\) is a primitive root modulo \(p\).