Past exam of the options I course of the University of Oxford / 2004 / C / C1

By the fundamental theorem of arithmetic, every integer greater than one has a prime factorization, and that factorization is unique up to reordering the factors. Equivalently, it has a unique finite prime-exponent representation $\boxed{n=\prod _p{p}^{v_p(n)}}$, with nonnegative integer exponents. The unit integer has the empty product.

Write $a={\prod }_p{p}^{r_p}$ and $b={\prod }_p{p}^{s_p}$. Divisibility is exactly comparison of prime exponents. Thus the greatest common divisor uses $\min (r_p,s_p)$ and the least common multiple uses $\max (r_p,s_p)$. Since their sum is $r_p+s_p$ for each prime,

Write $a=6r+1$ and $b=6s+1$. Then $ab=6(6rs+r+s)+1$, so $\boxed{ab\equiv 1(\mathrm{mod}6)}$. Repetition gives the same result for any finite product of numbers congruent to one.

Suppose only finitely many primes are congruent to five, and list them as $p_1,\dots ,p_k$. Consider $N=6p_1\cdots p_k-1>1$. It is divisible by neither two nor three, so every prime divisor is congruent to one or five modulo six. If all its prime factors were congruent to one, their product would be congruent to one by part (i), whereas $N\equiv 5$. Hence some prime divisor $q$ has $q\equiv 5(\mathrm{mod}6)$.

But no listed $p_i$ divides $N$, since $N\equiv -1(\mathrm{mod}{p}_i)$. This gives a new such prime, a contradiction. Therefore infinitely many primes are congruent to five modulo six. The argument does not require the specially constructed integer itself to be prime.