Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 2 / 1F (Number Theory)

Write $p=8k+7$. In Gauss's lemma, for the multiplier 2, precisely the integers $j$ with $p/4<j\le (p-1)/2$ give residues $2j>p/2$. Their number isIt is even, so the Legendre symbol $(2/p)=1$: 2 is a quadratic residue modulo $p$. For completeness, the sign rule follows by replacing those large residues by their negatives; the resulting absolute residues permute $1,\dots ,(p-1)/2$. Multiplying them and cancelling their nonzero product gives $2^{(p-1)/2}\equiv (-1{)}^{2k+2}=1(\mathrm{mod}p)$, equivalent to the residue assertion by Euler's criterion.

Now take the prime $p=2q+1$. The condition $q\equiv 3(\mathrm{mod}4)$ gives $p\equiv 7(\mathrm{mod}8)$, so $2^q\equiv 1(\mathrm{mod}p)$. Thus $p$ divides $2^q-1$. For integers $q>3$, $2^q-1>2q+1$ (true at 4 and preserved on increasing $q$), so this divisor is proper and $2^q-1$ is composite. At $q=3$, the divisor is the number itself: $2^3-1=2\cdot 3+1=7$. The congruence still holds, but it does not establish compositeness.