Euclid's GCD Algorithm

6.2 Euclid’s GCD Algorithm Euclid’s algorithm is an efficient method for computing the greatest common divisor of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. The Division Lemma. For any two integers \( a \) and \( b \) (where \( b \neq 0 \)), there exist unique integers \( q \) and \( r \) such that: \[ a = bq + r, \quad 0 \le r < |b| \] The algorithm relies on the property: \[ \gcd(a, b) = \gcd(b, r) \] The Process. To find \( \gcd(a, b) \), repeat the division until the remainder becomes zero. The last non-zero remainder is the GCD. 1. Divide \( a \) by \( b \) to get \( a = bq_1 + r_1 \). 2. Replace \( (a, b) \) with \( (b, r_1) \) and divide: \( b = r_1 q_2 + r_2 \). 3. Continue this until \( r_n = 0 \). 4. \( \gcd(a, b) = r_{n-1} \). Example: \( \gcd(252, 105) \) \[ 252 = 105 \times 2 + 42 \] \[ 105 = 42 \times 2 + 21 \] \[ 42 = 21 \times 2 + 0 \] Since the remainder is now 0, \( \gcd(252, 105) = 21 \).