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

The euclidean algorithm computes the greatest common divisor of two integers by repeated division with remainder. Start with $r_0=|A|$, $r_1=|B|$, interchanging them if necessary, and repeatedly writeuntil a zero remainder occurs. The positive remainders strictly decrease, so the process terminates. At each step the common divisors of $r_{j-1},r_j$ are exactly the common divisors of $r_j,r_{j+1}$, because $r_{j+1}=r_{j-1}-q_j{r}_j$. HenceIf one input is zero, the answer is the absolute value of the other; the usual convention sets $\gcd (0,0)=0$. Back-substitution also expresses the greatest common divisor as an integer linear combination of the inputs, as in Bézout's identity.

Let $P=3x^4-5x^3+2x^2-3x+2$ and $Q=3x^3+x^2+x-2$. Applying polynomial long division gives the euclidean algorithmThus their polynomial greatest common divisor is $3x-2$, up to a nonzero constant factor. Their unique common root of a polynomial is therefore

The polynomial factors as $p(x)=(3x-2{)}^2(3x+1)$, so $\alpha =2/3$ is a multiple root of multiplicity two. The Newton root-finding iteration isFor $x\ne 0,2/3$, cancelling a factor givesThis expression extends continuously to $g(2/3)=2/3$. Let $I=[1/3,1]$. On this closed interval,Thus $g$ is increasing, andBy the mean value theorem, $|g(x)-g(y)|\le (16/27)|x-y|$ for all $x,y\in I$. The contraction mapping theorem states that a contraction mapping from a nonempty complete metric space into itself has a unique fixed point, and every fixed-point iteration converges to it. The closed interval $I$ with ordinary Euclidean distance is complete, and $g(2/3)=2/3$, soIn fact $|x_k-2/3|\le (16/27{)}^k|x_0-2/3|$. The Newton iteration at a multiple root here has linear convergence, since $g^{\prime }(2/3)=1/2$. Thus the convergence assertion is true for the simplified fixed-point iteration, and for the usual Newton root-finding iteration that stops upon reaching an exact root of a polynomial. If one insists on applying the unsimplified quotient at every step, it is undefined for the allowed starting value $x_0=2/3$, since both $p$ and $p^{\prime }$ vanish there; that literal version of an infinite sequence requires the stated stopping convention or continuous extension.