The Euclidean Algorithm

4.3. The Euclidean Algorithm One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers. Greatest Common Divisor Recall that nonzero b is defined to be a divisor of a if a = mb for some m, where a, b, and m are integers. We will use the notation gcd(a, b) to mean the greatest common divisor of a and b. The positive integer c is said to be the greatest common divisor of a and b if c is a divisor of a and of b; any divisor of a and b is a divisor of c. An equivalent definition is the following: gcd(a, b) = max[k, such that k|a and k|b] Because we require that the greatest common divisor be positive, gcd(a, b) = gcd(a, b) = gcd(a, b) = gcd(a, b). In general, gcd(a, b) = gcd(|a|, |b|). gcd(60, 24) = gcd(60, 24) = 12 Also, because all nonzero integers divide 0, we have gcd(a, 0) = |a|. We stated that two integers a and b are relatively prime if their only common positive integer factor is 1. This is equivalent to saying that a and b are relatively prime if gcd(a, b) = 1. 8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and the positive divisors of 15 are 1, 3, 5, and 15, so 1 is the only integer on both lists.