Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 1 / c / i

Let $d=\gcd (c,n)$, and write $c=d{c}^{\prime }$, $n=d{n}^{\prime }$ with positive integers $c^{\prime },n^{\prime }$. If an integer $e>1$ divided both $c^{\prime }$ and $n^{\prime }$, then $de$ would divide both $c$ and $n$, contradicting the maximality of their greatest common divisor $d$. Thus $\gcd (c^{\prime },n^{\prime })=1$. Equivalently, Bézout's identity for $c,n$ can be divided by $d$ to express $1$ as an integer combination of $c^{\prime },n^{\prime }$.