Skip to main content

Exercises 17.7 Exercises

2.

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

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\text{.}\) Then solve them.

5.

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

6.

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

7.

In Exercise 16.8.9, you explored \(\sum_{a\in Q_p} a\text{.}\) Now suppose \(p\equiv 1\) (mod \(4\)); prove that the sum of the quadratic residues of \(p\) and the sum of the quadratic nonresidues are the same by computing both. (See [E.7.31] for a more complex but analogous statement for the case \(p\equiv 3\) (mod \(4\)), along with an elementary proof thereof.)

In Example 17.5.4 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\text{,}\) 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\text{,}\) then \(a\) is a QR modulo \(p\) if and only if \(p-a\) is not a QR.

10.

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

11.

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

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)\text{.}\) (Remember, \(n\) has to be odd by Definition 17.4.9.)

13.

Verify Fact 17.4.10 by coming up with four Jacobi symbols which evaluate to \(1\text{,}\) but for which you verify \(a\) is not a quadratic residue of \(n\text{.}\) (For your first one, why not use \(\left(\frac{3}{35}\right)\text{?}\))

14.

Learn about the Goldwasser–Micali public key encryption method. How is it implemented? What mathematics from this chapter is used?

15.

Make up and compute some Legendre symbols that seem pretty hard by using the Jacobi symbol instead.

17.

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

18.

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

19.

Use quadratic reciprocity to find a congruence criterion for when \(5\) is a quadratic residue for an odd prime \(p>5\text{.}\)

20.

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.14? See [E.7.10] about a story behind this unusual result.)

21.

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

22.

Explore the Solovay-Strassen primality test. Try implementing it well enough to check whether a number other than \(221\) is prime.

23.

Compute two nontrivial (that is, not obviously perfect square) Jacobi symbols for the odd composite number \(n=35\text{;}\) then do the same for \(n=943\text{.}\)