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

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.