Definition
Largest divisor
gcd(a, b) divides both; gcd = 1 means coprime.
Find GCD in JavaScript
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), gcd, a live preview, worked JavaScript 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.
gcd + lcm
Helper
Reuse gcd in lcm and fraction reduction.
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 Math.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).
JavaScript
// gcd(48, 18) = 6
// gcd(17, 13) = 1 (coprime)
// gcd(0, 21) = 21Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | number | Any integers (we normalize with Math.abs). |
| Return | number | Nonnegative gcd (0 for the (0, 0) convention here). |
Minimal workflow
Pseudocode
function gcd(a, b):
a = Math.abs(a)
b = Math.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 |
gcd | Helper function | Reuse in lcm and real projects |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Normalize | a = Math.abs(a); b = Math.abs(b) |
| Euclid step | a, b = b, a % b |
| Stop | while b != 0 then return a |
| Helper | gcd(a, b) |
| LCM | Math.abs(a * b) / gcd(a, b) |
| Classic | gcd(48, 18) = 6 |
Compare
📋 Iterative vs Recursive vs Helper
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
Helper
gcd()Reuse in lcm and fraction code
Interview tip
write EuclidThen mention 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 JavaScript programs — iterative Euclid, recursive Euclid, and a gcd helper with LCM. 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.
JavaScript
function findGcd(num1, num2) {
num1 = Math.abs(num1);
num2 = Math.abs(num2);
while (num2 !== 0) {
[num1, num2] = [num2, num1 % num2];
}
return num1;
}
const number1 = 48;
const number2 = 18;
const g = findGcd(number1, number2);
console.log(`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).
JavaScript
function gcdRecursive(a, b) {
a = Math.abs(a);
b = Math.abs(b);
if (b === 0) {
return a;
}
return gcdRecursive(b, a % b);
}
const number1 = 48;
const number2 = 18;
console.log(`GCD of ${number1} and ${number2} is: ${gcdRecursive(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)).
⚙️ GCD + LCM
Reuse gcd in the lcm formula for pairs of integers.
Example 3 — GCD Helper and LCM
Shared gcd helper plus the classic LCM identity.
JavaScript
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function lcm(a, b) {
if (a === 0 || b === 0) {
return 0;
}
return Math.abs(a * b) / gcd(a, b);
}
for (const [a, b] of [[48, 18], [17, 13], [0, 21], [-12, 18]]) {
const g = gcd(a, b);
console.log(`gcd(${a}, ${b}) = ${g}, lcm = ${lcm(a, b)}`);
}How It Works
Prefer a tested gcd helper in real projects (it also handles negatives). In interviews, write Euclid yourself first, then mention helper utilities and the LCM identity.
🧠 How the Algorithm Decides
1
Normalize
Set a = Math.abs(a), b = Math.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 findGcd(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: |a*b| / 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 gcd as follow-ups.
Usage Tips
Small habits that keep GCD solutions interview-ready.
1. Normalize with Math.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 Math.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 JavaScript numbers are IEEE doubles; use Math.abs(a / g * b) or divide before multiply when values are huge.
5. Forgetting gcd(0, n) = |n|
Special-casing zero incorrectly.
→ Euclid already handles it if Math.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
JavaScript 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 |
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 gcd in production.
Practice the three examples above, then continue to LCM to pair gcd with the classic identity.
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 Math.abs()
- Prefer iterative in interviews
- Define gcd(0, 0)
- Mention 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 Math.abs()
Guard 04
Helper
gcd + lcm
Reuse 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.
Yes when you normalize with Math.abs first; ES remainder uses truncated division toward zero.
Both are correct; iterative uses constant extra space.
O(log min(a,b)) Euclidean steps in the worst case.
For nonzero a and b, lcm(a,b) = |a*b| / gcd(a,b).
Use the Try it Yourself links under each code sample — they open an in-browser editor with the same logic so you can edit the input and Run.
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 LCM
Learn how to find the least common multiple using the gcd identity.
About the author
9 people found this page helpful