Past exam of the options II course of the University of Oxford / 2004 / C / C2

The Legendre symbol isThe distinction between the zero class and a nonzero quadratic residue is essential.

Euler's criterion statesFor $p\nmid a$ the right side is $+1$ or $-1$. The displayed congruence also holds for $p\mid a$, since $p$ is odd and the exponent is positive.

For distinct odd primes,Equivalently the two Legendre symbols agree unless both primes are three modulo four, in which case their signs are opposite. Neither symbol is zero here.

Quadratic reciprocity with the prime three givesThe latter symbol is $+1$ when $p\equiv 1(\mathrm{mod}3)$ and $-1$ when $p\equiv 2(\mathrm{mod}3)$. A prime greater than three occupies one of the classes $1,5,7,11$ modulo twelve. Combining its residues modulo three and four gives signs $+1,-1,-1,+1$ respectively. Hence

For $n\ge 1$, the exponent $2^n$ is positive and even. Since $2^{2j}=4^j\equiv 4(\mathrm{mod}12)$ for every $j\ge 1$, it follows thatHere the natural-number indexing must start at one. If zero is included in that convention, $F_0=3$ is an exception to the printed assertion and must be excluded.

Let $p=F_m$ be prime with $m\ge 1$. The preceding parts give $(3/p)=-1$, so Euler's criterion implies $3^{(p-1)/2}\equiv -1(\mathrm{mod}p)$. The multiplicative order $d$ of three divides $p-1=2^{2^m}$. Every proper divisor of this power of two divides $(p-1)/2$. If $d$ were proper, that half-power would be one, a contradiction. Thereforewhich means precisely that three is a primitive root modulo $p$.