Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 4 / 9H (Number Theory)

The Chinese remainder theorem says that for pairwise coprime positive moduli $n_i$, arbitrary residue classes modulo each $n_i$ specify one residue class modulo ${\prod }_i{n}_i$. For an odd positive integer $N=\prod p_i^{e_i}$, the Jacobi symbol is $(a/N)={\prod }_i(a/p_i{)}^{e_i}$, where each factor is a Legendre symbol; for $N=1$ the empty product is one. The Jacobi symbol is multiplicative in $a$, and is zero exactly when $a$ and $N$ have a common prime factor.

False. The Jacobi symbol $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, yet $2$ is not a quadratic residue modulo three. A solution modulo fifteen would give one modulo three, which is impossible. A positive Jacobi symbol need not indicate a square modulo a composite modulus.

True. Since $N$ is not a square, some exponent $e_i$ is odd. Choose a quadratic nonresidue modulo that $p_i$ and choose residue one at every other prime. The Chinese remainder theorem produces a unit $b$ modulo $N$ with $(b/N)=-1$. Multiplication by $b$ permutes the residue classes modulo $N$. Thus, by multiplicativity of the Jacobi symbol,The sum is therefore $\boxed{0}$. Nonunits contribute zero, so the permutation argument covers every term.

False. The Carmichael number $561=3\cdot 11\cdot 17$ supplies a counterexample. For every $a$ coprime to $561$, the Fermat little theorem gives $a^{560}\equiv 1$ modulo each of these primes, since $2,10,16$ all divide $560$. The Chinese remainder theorem then gives $a^{560}\equiv 1(\mathrm{mod}561)$. Thus the proposed Fermat primality test can fail to detect a composite for every coprime base.

True. First suppose $p^e\mid N$ with $e\ge 2$ maximal. By the Chinese remainder theorem, choose $a\equiv 1+p^{e-1}(\mathrm{mod}{p}^e)$ and $a\equiv 1$ modulo all other prime-power factors. This is a unit, with Jacobi symbol one, because it is one modulo every prime. For $m=(N-1)/2$, the binomial theorem givesbecause $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.

If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a quadratic nonresidue at one prime $p$ and one at every other prime, again using the Chinese remainder theorem. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv 1\not\equiv -1(\mathrm{mod}q)$. These two cases prove that every odd composite has an Euler-Jacobi witness, unlike the situation for the ordinary Fermat primality test.