GCD: Euclidean Remainder Pattern

Learning Outcome

After this lesson, you should be able to replace gcd(a,b) with gcd(b,a mod b) until the remainder becomes zero.

Problem Statement

Given two integers a and b, return their greatest common divisor.

Brute Force Approach

Check every possible divisor from min(a,b) down to 1. This can be slow when numbers are large.

Optimized Approach

Use the identity gcd(a,b) = gcd(b,a mod b). Repeated remainders shrink the numbers quickly.

Exact Pseudocode

while b is not 0:
  remainder = a % b
  a = b
  b = remainder
return absolute value of a
  

Reference Code

class Solution:
    def gcd(self, a, b):
        while b != 0:
            a, b = b, a % b
        return abs(a)
  

Sample Dry Run

Complexity

Edge Cases

• gcd(a,0) is absolute value of a.
• gcd(0,b) is absolute value of b.
• Normalize negative inputs with absolute value at the end.

Interview Checklist

• Use modulo, not repeated subtraction.
• Stop when the second value becomes zero.
• Return the nonzero value as positive.

FAQs

Any divisor of a and b also divides the remainder after removing multiples of b.

Modulo removes many repeated subtraction steps in one operation.

Euclidean remainder reduction.