Definition
Largest divisor
gcd(a, b) divides both; gcd = 1 means coprime.
Find GCD in Python
Overview
What You’ll Learn
The GCD of two integers is the largest positive integer that divides both. This tutorial covers Euclid’s algorithm (iterative and recursive), math.gcd, a live preview, worked Python examples, edge cases, and complexity.
Euclid Rule
gcd(b, a%b)
Remainders shrink until b becomes 0.
Classic 48, 18
gcd = 6
Trace: 48→18→12→6→0.
math.gcd
Builtin
Best for real code after you can write Euclid.
Live Preview
Try a, b
Compute gcd on magnitudes in the browser.
O(log min)
Euclid steps
Worst case near consecutive Fibonacci pairs.
Introduction
The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b. Euclid’s rule gcd(a, b) = gcd(b, a % b) reduces the pair until the remainder is zero — then the leftover value is the answer.
Example: gcd(48, 18) = 6. If gcd is 1, the numbers are coprime. Also, lcm(a, b) = |a b| / gcd(a, b) for nonzero pairs.
Why it matters?
GCD underpins fraction reduction, modular inverses, Diophantine equations, and many interview number-theory warm-ups.
Key Highlights
Euclid Step
(a, b) ← (b, a % b).
Stop at 0
When b = 0, return a.
Use abs()
Keep the result nonnegative.
gcd(0, n)
Equals |n| for n ≠ 0.
In short: replace (a, b) with (b, a % b) until b is 0; the leftover a is the gcd.
Foundation
📝 Problem & Approach
Given integers a and b, compute gcd(a, b).
python
# gcd(48, 18) = 6
# gcd(17, 13) = 1 (coprime)
# gcd(0, 21) = 21Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | int | Any integers (we normalize with abs). |
| Return | int | Nonnegative gcd (0 for the (0, 0) convention here). |
Minimal workflow
Pseudocode
function gcd(a, b):
a = abs(a)
b = abs(b)
while b != 0:
(a, b) = (b, a mod b)
return aMethod comparison
| Method | Idea | Notes |
|---|---|---|
| Iterative Euclid | Loop with % | O(1) extra space — interview default |
| Recursive Euclid | gcd(b, a % b) | Matches the math formula closely |
math.gcd | Builtin | Best for production code |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Normalize | a, b = abs(a), abs(b) |
| Euclid step | a, b = b, a % b |
| Stop | while b != 0 then return a |
| Builtin | math.gcd(a, b) |
| LCM | abs(a * b) // gcd(a, b) |
| Classic | gcd(48, 18) = 6 |
Compare
📋 Iterative vs Recursive vs Builtin
Same Euclidean math — pick by clarity and constraints.
Iterative
while b: a,b=b,a%bO(1) space — best default
Recursive
gcd(b, a % b)Reads like the textbook rule
Builtin
math.gcdShip this in real projects
Interview tip
write EuclidThen mention math.gcd / binary gcd
Context
When This Problem Shows Up
Reach for GCD whenever common divisors or modular structure matter.
Interview warm-ups
Classic modulo + loop problem with log-time analysis.
Fraction reduction
Divide numerator and denominator by gcd.
Modular inverses
Inverse of a mod m exists when gcd(a, m) = 1.
After Fibonacci
Worst-case Euclid pairs are consecutive Fibonacci numbers.
Define gcd(0, 0)
State the convention (often 0) before coding.
Key benefit: a short log-time algorithm that unlocks fractions, LCM, and modular arithmetic.
Interactive
🔮 Live Preview
Enter two integers (safe range). We compute gcd on magnitudes.
Hands-On
Examples Gallery
Three complete Python programs — iterative Euclid, recursive Euclid, and math.gcd. Click View Output to reveal sample console results.
📚 Getting Started
Interview-default loop with constant extra space.
Example 1 — Iterative Euclidean Algorithm
Uses a loop to compute gcd for 48 and 18.
python
def find_gcd(num1: int, num2: int) -> int:
num1, num2 = abs(num1), abs(num2)
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
number1 = 48
number2 = 18
g = find_gcd(number1, number2)
print(f"GCD of {number1} and {number2} is: {g}")How It Works
Each loop step keeps the gcd unchanged and reduces the second value until it becomes zero. The leftover first value is the answer.
⚡ Recursive Style
Same remainder chain, written as a recurrence.
Example 2 — Recursive Euclidean Algorithm
Base case b == 0; otherwise recurse on (b, a % b).
python
def gcd_recursive(a: int, b: int) -> int:
a, b = abs(a), abs(b)
if b == 0:
return a
return gcd_recursive(b, a % b)
number1 = 48
number2 = 18
print(f"GCD of {number1} and {number2} is: {gcd_recursive(number1, number2)}")How It Works
Recursive calls follow the same remainder chain as iterative Euclid, then return the final nonzero value. Stack depth is O(log min(a, b)).
⚙️ Builtin Style
Use the standard library when you do not need to reinvent Euclid.
Example 3 — math.gcd and LCM
Builtin gcd plus the classic LCM identity.
python
import math
def lcm(a: int, b: int) -> int:
if a == 0 or b == 0:
return 0
return abs(a * b) // math.gcd(a, b)
for a, b in ((48, 18), (17, 13), (0, 21), (-12, 18)):
g = math.gcd(a, b)
print(f"gcd({a}, {b}) = {g}, lcm = {lcm(a, b)}")How It Works
Prefer math.gcd in real projects (it also handles negatives). In interviews, write Euclid yourself first, then mention the builtin and the LCM identity.
🧠 How the Algorithm Decides
1
Normalize
Set a = abs(a), b = abs(b).
Signs
2
Euclidean loop
While b != 0, replace (a, b) with (b, a % b).
Reduce
3
Stop
When b is 0, a is the gcd.
Done
=
gcd(a, b)
Largest nonnegative common divisor.
Trace
🔎 Worked Walkthrough — gcd(48, 18)
Trace the Euclidean remainder chain for the classic interview pair.
| Step | (a, b) | a % b | Next |
|---|---|---|---|
| 1 | (48, 18) | 12 | (18, 12) |
| 2 | (18, 12) | 6 | (12, 6) |
| 3 | (12, 6) | 0 | (6, 0) |
| 4 | (6, 0) | — | return 6 |
Final answer: gcd(48, 18) = 6.
Use Cases
Where GCD shows up beyond the interview prompt.
1. Interview Warm-Ups
Modulo loops with clear log-time analysis.
Example: write find_gcd(a, b).
2. Fraction Reduction
Simplify p/q by dividing by gcd.
Example: 18/48 → 3/8.
3. LCM via GCD
Compute least common multiple safely.
Example: |ab| // gcd(a, b).
4. Modular Arithmetic
Check coprimality for inverses.
Example: gcd(a, m) = 1.
5. Common Divisors
GCD is the largest shared divisor.
Example: related interview page.
6. Bézout Follow-Ups
Extended Euclid finds x, y with ax + by = gcd.
Example: mention if asked for identity.
Pro Tip: say “gcd(a, b) = gcd(b, a % b)” before coding — it proves you know the invariant.
Advantages
Why Euclid works well in interviews and classwork.
1. Tiny Code
A few lines encode a deep number-theory idea.
2. Fast
O(log min(a, b)) steps in practice.
3. Two Valid Styles
Iterative and recursive both match the math.
4. Rich Follow-Ups
LCM, extended Euclid, and binary gcd.
Pro Tip: lead with iterative Euclid; offer recursive and math.gcd as follow-ups.
Usage Tips
Small habits that keep GCD solutions interview-ready.
1. Normalize with abs()
Keep the returned gcd nonnegative.
2. State gcd(0, 0)
Say your convention (often 0) up front.
3. Spot-Check 48, 18
Expect 6; also try (0, 21) and (17, 13).
4. Prefer Iterative in Interviews
O(1) space and no recursion-depth worry.
5. Mention LCM
Show you know |ab| / gcd when asked.
Pro Tip: worst-case Euclid step counts appear on consecutive Fibonacci inputs — a nice follow-up after the Fibonacci page.
Common Pitfalls
Mistakes that commonly break GCD solutions.
1. Skipping abs()
Negative inputs can yield a negative-looking remainder story.
→ Normalize with abs first.
2. Undefined gcd(0, 0)
Crashing or returning nonsense.
→ Document convention (often return 0).
3. Brute-Force From min Down
Looping from min(a, b) to 1 is O(min) and slow.
→ Use Euclid instead.
4. LCM Overflow Carelessness
Computing a * b before dividing in fixed-width languages.
→ In Python ints grow; still prefer abs(a // g * b) patterns when careful.
5. Forgetting gcd(0, n) = |n|
Special-casing zero incorrectly.
→ Euclid already handles it if abs is applied.
Edge Cases
Normalize signs and define behavior for gcd(0, 0) explicitly.
Zero pair
gcd(0, 0)
Many implementations return 0 by convention.
One zero
gcd(0, n)
Equals |n| for n ≠ 0.
Sign
Negative inputs
Use absolute values to keep gcd nonnegative.
Order
gcd(a, b) = gcd(b, a)
Input order does not change the answer.
Coprime
gcd = 1
Numbers share no common divisor greater than 1.
Huge ints
Big integers
Python supports them; runtime grows with digit length.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Invariant. gcd(a, b) = gcd(b, a % b); common divisors are preserved.
- LCM. For nonzero a, b: lcm(a, b) = |a b| / gcd(a, b).
- Bézout. There exist integers x, y with ax + by = gcd(a, b).
- Worst case. Consecutive Fibonacci numbers maximize Euclid steps.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Verify classics
- (48, 18) → 6
- (17, 13) → 1
2. Match both styles
- Iterative vs recursive
- Assert identical results
3. Zero cases
- gcd(0, 21) = 21
- Decide gcd(0, 0)
4. Reduce a fraction
- 18/48 → 3/8
- Divide by gcd
Important
Notes
- Rule: gcd(a, b) = gcd(b, a % b) until b = 0.
- Code: iterative and recursive versions both match the math.
- Watch-outs: define gcd(0, 0) and normalize sign.
- Time is O(log min(a, b)); iterative uses O(1) extra space.
Quick Takeaway: keep replacing (a, b) with (b, a % b) until b is 0; the leftover a is the gcd.
Analysis
⏱️ Time and Space Complexity
| Version | Time | Extra space |
|---|---|---|
| Iterative Euclid | O(log min(a, b)) | O(1) |
| Recursive Euclid | same | O(log min(a, b)) stack |
math.gcd | same order | O(1) |
Worst-case step count appears on consecutive Fibonacci inputs.
🎉 Conclusion
GCD is the largest nonnegative common divisor. Euclid reduces (a, b) via remainders until b is 0; write it iteratively in interviews and use math.gcd in production.
Practice the three examples above, then continue to happy numbers for a digit-square cycle problem.
Normalize signs, define gcd(0, 0), and mention the LCM identity when asked.
Pro Tips
💡 Best Practices
✅ Do
- State Euclid’s rule first
- Normalize with abs()
- Prefer iterative in interviews
- Define gcd(0, 0)
- Mention math.gcd and LCM
❌ Don’t
- Brute-force from min downward
- Ignore negative inputs
- Leave gcd(0, 0) undefined
- Skip the remainder invariant
- Forget coprime means gcd = 1
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about GCD
Compute gcd the interview-friendly way.
5
Core concepts 01
Rule
gcd(b, a%b)
Euclid 02
Stop
b = 0 → a
Base 03
Signs
use abs()
Guard 04
Builtin
math.gcd
Ship 05
Cost
O(log min)
Analysis❓ Frequently Asked Questions
It is the largest positive integer that divides both numbers.
For n > 0, gcd(0, n) = n. Many libraries define gcd(0,0) as 0.
Repeat (a, b) <- (b, a % b) until b becomes 0. Then a is the gcd.
Yes, usually we compute gcd on absolute values so the result is nonnegative.
Both are correct; iterative uses constant extra space.
O(log min(a,b)) Euclidean steps in the worst case.
Yes for real code. In interviews, write Euclid yourself, then mention the builtin.
For nonzero a and b, lcm(a,b) = |a*b| / gcd(a,b).
Did you Know? 🔊
Bézout's identity: for integers a, b not both zero, there exist integers x, y such that gcd(a,b) = a x + b y.
Continue to Happy Number
Learn how happy numbers use repeated sums of squared digits until they reach 1 or a cycle.
About the author
9 people found this page helpful