Chapter 13 Appendix D - Euclidean Algorithm

Practice using the Euclidean Algorithm

Pick two integers, \(a\) and \(b\), and calculate their greatest common divisor, \(d=\gcd(a,b)\). Then apply Bezout’s Identity to find two integers \(u, v\) such that \(\gcd(a,b) = au + bv\).

As an example, try the following values

Now check your answers by entering your values of \(a\) and \(b\) in the boxes labelled ‘a’ and ‘b’ below and hit the “Euclidean Algorithm” button. The left hand table will show the outcome of the Euclidean Algorithm, whilst the right hand table will display the outcome of Bezout’s Identity.

 

a b