2.4 The Euclidean Algorithm
$ a =qb + r \Rightarrow gcd(a,b) = gcd(b,r) $
164 published posts · Page 17 of 28

$ \text{Given } a,b \in \mathbb{Z} \text{ (at least one of them is not zero), } $


Let $a,b\in \mathbb{Z} $. The greatest common divisor of a and b is the positive integer d satisfying


Let a=61 and b=-7 then 61 = (-8)(-7) + 5, hence q = -8 and r = 5
