The Euclidean Algorithm

By K. Houston. Numbers and Symmetry, 2020

77 citations recorded by the source corpus.

xn = xn 2 an 1xn 1 with 0  xn 2 < xn 1. The algorithm terminates when xn = 0. (74) Compute the sequences xn and an with x0 = 321 and x1 = 123. (75) Show that GCD(x0, x1) = GCD(x1, x2) = · · · = GCD(xn 1, xn) = xn 1, where xn = 0. Let this common GCD be g. (76) Show that there is an elementary matrix E with E ⇥ xn 2 xn 1 ⇤ = E [ xn xn 1 ]. (77) Show that there is a product of elementary matrices F , with F [ x0 x1 ] = [ g 0 ]. (78) Show that there exist sequences bk and ck such that bkxk + ckxk+1 = g and show how to compute the b’s and c’s using the a’s. (79) Demonstrate that your method works by finding b and c such that b · 321 + c · 123 = 3.

Subfields: Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/0a609427d229ca5b2b2c81446b6b4339e605b82c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

1. M. Ram Murty
2. Malcolm Harper

Citations in the corpus

• Euclidean Rings of Algebraic Integers (2004, background): “Proposition 6 (Gupta-Murty [GM]) Let K be an algebraic number e ld. Let M be a monoid in OK and for p coprime to the elements of M, denote by fM(p) the order of M mod p. If M contains r multiplicatively independent elements, then #fp : fM(p) Yg Y (r+1)=r :”