Past exam of the mathematics course of the University of Cambridge / 2023 / ia / Paper 4 / 6E / Solution

For prime $p$, the nonzero residues pair with their distinct inverses except for $1$ and $-1$, so Wilson theorem givesIf composite $n>4$ has a factorization $n=ab$ with $1<a<b<n$, both factors occur in $(n-1)!$. If $n=m^2$, the distinct factors $m$ and $2m$ occur and their product is divisible by $n$; the excluded case $m=2$ is exactly $n=4$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$.

The Fermat-Euler theorem states $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ when $(a,n)=1$. For prime $p$, $\varphi (p)=p-1$, giving Fermat's little theorem for $p\nmid a$; the form $a^p\equiv a(\mathrm{mod}p)$ also covers $p\mid a$.

If $a\equiv b(\mathrm{mod}p)$, induction and the binomial theorem showIndeed, write $a^{p^n}=b^{p^n}+c{p}^{n+1}$ and raise to the $p$th power; every nonleading binomial term gains enough powers of $p$.

Fix $a>1$ and choose any odd prime $p\nmid a^2-1$. PutFermat's theorem gives $N_p\equiv 1(\mathrm{mod}p)$, and $N_p$ is odd, so $2p\mid N_p-1$. Also $a^{2p}\equiv 1(\mathrm{mod}{N}_p)$, hence $a^{N_p-1}\equiv 1(\mathrm{mod}{N}_p)$. For odd $p$,is composite. This generalized repunit pseudoprime construction gives infinitely many distinct base-$a$ pseudoprimes because the values are unbounded.

Solved by gpt-5.6-sol high.