Past exam of the options II course of the University of Oxford / 2005 / C

Euler's totient function $\varphi (n)$ counts the integers $1\le a\le n$ coprime to $n$, equivalently the invertible residue classes modulo $n$. Among $1,\dots ,p^e$, exactly the $p^{e-1}$ multiples of $p$ are not coprime to the prime power. HenceFactor $n={\prod }_p{p}^{e_p}$. Its distinct prime-power factors are pairwise coprime, so the permitted multiplicativity givesFor $n=1$, the empty product is one and agrees with $\varphi (1)=1$.

Use prime factorization and multiplicativity to check the identity one prime at a time. Fix $p$ and put $a=v_p(m)$, $b=v_p(n)$, $r=\min (a,b)$. The local factors to compare areIf either exponent is zero, $r=0$ and the equality follows from $\varphi (1)=1$. If both are positive, the prime-power formula makes both sidesMultiplying the local identities over all primes and using $\gcd (m,n)={\prod }_p{p}^{\min (v_p(m),v_p(n))}$ givesThis accounts for repeated prime factors shared by the two inputs, which ordinary coprime multiplicativity alone would not remove.

Fermat's little theorem states that for a prime $p$ and an integer $a$ not divisible by $p$,Equivalently, $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$, with divisibility by $p$ allowed in that latter formulation.

Since $n>1$, its factorial is even, so $(n!{)}^2+1$ is odd and its prime divisor $p$ is odd. Also $p$ cannot divide $n!$, since it would then divide1. Modulo $p$,Raise this equation to the integer power $(p-1)/2$. Fermat's little theorem givesAs $p$ is odd, $1$ and $-1$ are distinct residues. Thus the exponent is even, and

If a prime divisor $p$ of $(n!{)}^2+1$ satisfied $p\le n$, it would divide $n!$ and therefore divide the difference $(n!{)}^2+1-(n!{)}^2=1$, impossible. Hence $p>n$.

Every integer $(n!{)}^2+1>1$ has a prime divisor, and (ii) makes each of its prime divisors congruent to 1 modulo 4. Taking arbitrarily large $n$ produces such primes beyond every bound. ThereforeEquivalently, if their list were finite, choosing $n$ at least its largest member would produce a new member larger than that supposed maximum.