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 / iii / Solution

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.