State the Chinese remainder theorem. Let $n$ be an odd positive integer. If $n$ is divisible by the square of a prime number $p$, prove that there exists an integer $z$ such that $z^{p} \equiv 1(\bmod n)$ but $z \not \equiv 1(\bmod n)$.

Define the Jacobi symbol

$$\left(\frac{a}{n}\right)$$

for any non-zero integer $a$. Give a numerical example to show that

$$\left(\frac{a}{n}\right)=+1$$

does not imply in general that $a$ is a square modulo $n$. State and prove the law of quadratic reciprocity for the Jacobi symbol.

[You may assume the law of quadratic reciprocity for the Legendre symbol.]

Assume now that $n$ is divisible by the square of a prime number. Prove that there exists an integer $a$ with $(a, n)=1$ such that the congruence

$$a^{\frac{n-1}{2}} \equiv\left(\frac{a}{n}\right) \quad(\bmod n)$$

does not hold. Show further that this congruence fails to hold for at least half of all relatively prime residue classes modulo $n$.