NTIC Exercises

Exercises 17.7 Exercises

1.

Evaluate the Legendre symbols for $p=11$ and $a=2,3,5$ using Eisenstein's Criterion for the Legendre Symbol.

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

🔗

3.

Do any Legendre symbols in Example 17.1.5 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\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 [C.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.8.)

🔗

13.

Verify Fact 17.4.9 by coming up with four Jacobi symbols which evaluate to $1\text{,}$ but for which $a$ is not a quadratic residue of $n\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.

🔗

16.

If you didn't do them already, do the exercises in Example 17.4.7.

🔗

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 [C.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{.}$