Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 3 / b

Use strong induction on the positive integer $n$. The case $n=1$ is represented by the empty product. For $n>1$, if $n$ is prime it is already a product of one prime. Otherwise $n=ab$ with $1<a,b<n$; the induction hypothesis gives prime factorizations for both $a$ and $b$, and concatenating them gives one for $n$. This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.

If $p\mid a$, there is nothing to prove. Otherwise the only possible positive common divisors of the prime $p$ and $a$ show that $\gcd (p,a)=1$. By Bézout's identity, $up+va=1$ for some integers $u,v$. Multiplying by $b$ gives $b=upb+vab$. Both terms on the right are divisible by $p$, the second because $p\mid ab$. Hence $p\mid b$. This proves Euclid's lemma, including when either factor is zero or negative.

Suppose $n=p_1\cdots p_r=q_1\cdots q_s$ are two products of positive primes. If $r=0$, then $n=1$, and necessarily $s=0$, since any nonempty product of positive primes is at least $2$. Otherwise Euclid's lemma, applied repeatedly to the right-hand product, says $p_1$ divides one $q_j$. Since $q_j$ is prime, $p_1=q_j$. Reorder the right-hand factors and cancel this common nonzero factor. Repeating, or using induction on the number of factors, matches every factor. Neither side can have factors left over, because their product would then equal $1$. Thus the prime factorization is unique up to rearrangement.