Divisibility and factorization · Definition

Extended Euclidean algorithm

elementary number theorydivisibility and factorization

Before you start you need to know

The successive divisions of the Euclidean algorithm leave the greatest common divisor as a linear combination of the original numbers. Tracking the coefficients at each step produces that combination directly.

Definition

The extended Euclidean algorithm computes \(d=\gcd(a,b)\) and integers \(x\), \(y\) such that \(ax+by=d\). It is the Euclidean algorithm that also tracks the Bézout coefficients.

\[r_k=r_{k-2}-q_{k-1}r_{k-1}\\s_k=s_{k-2}-q_{k-1}s_{k-1}\\t_k=t_{k-2}-q_{k-1}t_{k-1}\]

Let \(r_{-1}=a\) and \(r_0=b\), with \(s_{-1}=1\), \(t_{-1}=0\), \(s_0=0\), \(t_0=1\). At each step divide \(r_{k-2}=q_{k-1}r_{k-1}+r_k\) and update the coefficients by the rule in the formula, so that \(r_k=a\,s_k+b\,t_k\) always holds. When the remainder vanishes, the last nonzero remainder is \(d\) and its coefficients are the desired ones; this invariant guarantees the Bézout identity.

For \(a=240\) and \(b=46\): \(240=5\cdot 46+10\), \(46=4\cdot 10+6\), \(10=1\cdot 6+4\), \(6=1\cdot 4+2\), \(4=2\cdot 2\). Thus \(d=2\). Back-substituting, \(2=6-4=2\cdot 6-10=2\cdot 46-9\cdot 10=47\cdot 46-9\cdot 240\), so \(x=-9\) and \(y=47\) satisfy \(240(-9)+46(47)=2\). The coefficient table gives the same result without substitutions.

A typical mistake is forgetting that the initial coefficients are \(s_{-1}=1\), \(t_{-1}=0\) and \(s_0=0\), \(t_0=1\), and starting with \(s_0=1\) or \(t_0=1\) for both. This produces a combination that does not match \(a\) and \(b\). Always check that \(ax+by=d\) with the final values.

Think about it

Why are \(x\) and \(y\) not unique?

Because \((x+kb/d,\ y-ka/d)\) also satisfies \(ax+by=d\) for every integer \(k\).

Exercises 10

  1. What does the extended Euclidean algorithm guarantee at termination?
  2. What are the initial values of \(s_{-1}\) and \(t_{-1}\)?
  3. If \(\gcd(a,b)=d\), what relation do \(a\), \(b\) and \(d\) satisfy in Bézout's identity?
  4. In the step \(46=4\cdot 10+6\) of the division \(r_{k-2}=q_{k-1}r_{k-1}+r_k\), what is \(q_{k-1}\)?
  5. What is \(\gcd(240,46)\) according to the algorithm?
  6. For \(a=30\) and \(b=12\), with \(6=30-2\cdot 12\), what value of \(y\) satisfies \(30x+12y=6\) with \(x=1\)?
  7. With \(a=35\) and \(b=15\), the algorithm gives \(\gcd=5\). Which is a valid pair \((x,y)\) with \(35x+15y=5\)?
  8. For \(a=17\) and \(b=5\), what is the coefficient \(y\) in the identity \(17x+5y=1\)?
  9. If the extended algorithm gives \(s_k\) and \(t_k\) with \(r_k=as_k+bt_k\), what must hold at the end of the process?
  10. For \(a=99\) and \(b=78\), with \(\gcd(a,b)=3\), which pair \((x,y)\) satisfies \(99x+78y=3\)?

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 2
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 1