Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 10G / a / Solution

Set $p_{-2}=0,p_{-1}=1,q_{-2}=1,q_{-1}=0$ and define the continued fraction convergents byThe recurrence reverses the sign of $p_n{q}_{n-1}-p_{n-1}{q}_n$, whose initial value at $n=0$ is $-1$. Hence $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$. Every common divisor of $p_n,q_n$ divides this number, proving $\boxed{\gcd (p_n,q_n)=1}$.