Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics IV resit / 7

Let $d$ be any positive integer. If $d$ divides $a$ and $b$, it divides the integer linear combination $a-qb=r$. Conversely, if $d$ divides $b$ and $r$, it divides $qb+r=a$. Thus $(a,b)$ and $(b,r)$ have exactly the same positive common divisors. Their greatest elements coincide:This greatest common divisor invariance is the step behind the Euclidean algorithm; it does not require $r<b$, although that additional bound ensures the algorithm terminates. If the convention $0\in \mathbb{N}$ permits $r=0$, the same argument works and $\gcd (b,0)=b$ for $b>0$.

The successive division with remainder steps of the Euclidean algorithm areEach step preserves the greatest common divisor by part (a). The final nonzero remainder is $9$, so

Back-substitute in the Euclidean algorithm to obtain an integer linear combination:Multiplying by $3$ gives the particular solution $(x_0,y_0)=(-45,21)$ of the linear Diophantine equation. Subtracting it from any other solution and dividing by $9$ givesThe integers $34$ and $73$ are coprime, so $73$ divides $x+45$. Writing $x+45=73t$ forces $y-21=-34t$. Conversely these expressions satisfy the original equation for every integer $t$. Thus all solutions of a linear Diophantine equation here are

Rearrange the polynomial equation as a fixed point equation:First establish existence and uniqueness of the target root of a polynomial. Since $f$ is a continuous function, $f(0)=-1<0$ and $f(1/7)=1/7^5>0$, the intermediate value theorem gives a root of a polynomial $\xi \in (0,1/7)$. Moreover $f^{\prime }(x)=5x^4+7>0$ for all real $x$, so $f$ is strictly increasing and this is its only real root of a polynomial.

For $x\in [0,1/7]$,so $g$ maps the closed interval into itself. AlsoThe mean value theorem therefore gives $|g(x)-g(y)|\le q|x-y|$ on the closed interval: $g$ is a contraction mapping. For any starting value $x_0\in [0,1/7]$, all iterates remain in that closed interval, and since $g(\xi )=\xi$,Thus the fixed-point iteration converges to the unique real root of a polynomial from every $x_0\in [0,1/7]$. This explicit error estimate proves the needed convergence directly.