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

The greatest common divisor of positive integers $a,b$ is the largest positive integer dividing both, denoted $\gcd (a,b)$. The set of positive common divisors contains $1$ and is finite, so this definition supplies a value.

The Euclidean algorithm repeatedly replaces $(r_{i-1},r_i)$ by $(r_i,r_{i-1}-q_i{r}_i)$, where the new remainder lies between $0$ and $r_i-1$. Common divisors are unchanged by this subtraction, and decreasing positive remainders ensure termination. The last nonzero remainder is the greatest common divisor.

The extended Euclidean algorithm also tracks coefficients $r_i=u_{i}a+v_{i}b$, beginning with coefficient pairs $(1,0)$ and $(0,1)$ and applying the same subtraction to the pairs. This invariant produces Bézout coefficients for the last nonzero remainder. Here the divisions areBack substitution givesThus $\gcd (580,252)=4$, with $m=10$ and $n=-23$ in Bézout's identity.

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.

The allowed primes are exactly $2,3,5,7$. DefineThe fundamental theorem of arithmetic makes this definition unambiguous and proves injectivity. For every $(a,b,c,d)\in {\mathbb{N}}^4$, the positive integer $2^a{3}^b{5}^c{7}^d$ belongs to $S$ and maps to that tuple, proving surjectivity. The inverse function is explicitly ${\Phi }^{-1}(a,b,c,d)=2^a{3}^b{5}^c{7}^d$. In particular, $1$ maps to $(0,0,0,0)$. This is the prime-exponent parametrization of smooth numbers.