18×48 6
- Idea
- largest square tile for both sides
Find GCD in JavaScript
What you’ll learn
- The definition of gcd(
a,b) for integers and the special casegcd(0, n) = |n|. - The Euclidean algorithm in an iterative form (like the reference) plus a compact recursive variant.
- Where gcd shows up in fraction reduction, linear Diophantine problems, and modular arithmetic.
Overview
Euclid’s rule gcd(a,b) = gcd(b, a mod b) shrinks the pair at every step until the remainder hits zero. The surviving value is the gcd—fast, tiny code, and standard in interviews.
Two programs
Iterative and recursive Euclidean, both for 48 and 18.
Live preview
Two integers (safe range); shows gcd with magnitudes if you enter negatives.
Rigor
Correct Euclidean wording, gcd(0,0) note, and ES remainder sign awareness.
Prerequisites
Integer division and remainder (/ and %), while loops, and functions.
console.log,Number.isSafeInteger,Math.abs.- Optional: recursion depth if you port naive recursion to huge integers.
What is gcd?
When a and b are not both zero, gcd(a,b) is the largest positive integer d such that d | a and d | b.
Among all positive linear combinations a x + b y with integers x, y, the smallest is gcd(a,b) (Bézout). Coprime pairs have gcd(a,b)=1.
48, 18 gcd = 6
Euclid gcd(a,b)=gcd(b,a%b)
LCM link |ab|/gcd
Reduction step
If b ≠ 0, any common divisor of a and b also divides a - q b for every integer q; taking q = floor(a/b) in the division algorithm yields a mod b. Hence gcd(a,b) = gcd(b, a mod b).
gcd(48, 18)gcd(48,18) = gcd(18, 48 mod 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.
Intuition
18/48 3/8
- Reduce
- divide by gcd 6
Takeaway: gcd is the last nonzero remainder in the Euclidean remainder chain.
Live preview
Integers in JavaScript safe range (magnitudes used if you enter negatives).
Algorithm
Goal: compute gcd(a,b) for integers, assuming typical interview inputs fit in Number.
Normalize (optional)
Replace a and b by their absolute values if you want a nonnegative gcd; handle (0,0) separately if needed.
Euclidean loop
While b ≠ 0, set (a,b) ← (b, a % b). When b === 0, return a.
📜 Pseudocode
Pseudocode
function gcd(a, b): // assume nonnegative; define gcd(0,0) as needed
while b != 0:
(a, b) = (b, a mod b)
return a1
Iterative Euclidean algorithm
Matches the reference logic for 48 and 18. Uses findGcd and two sample inputs.
JavaScript
function findGcd(num1, num2) {
while (num2 !== 0) {
const temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
const number1 = 48;
const number2 = 18;
const g = findGcd(number1, number2);
console.log("GCD of " + number1 + " and " + number2 + " is: " + g);Explanation
Each iteration stores the old b in num1 and replaces b by a mod b. When b becomes 0, num1 holds the gcd.
2
Recursive Euclidean algorithm
Same result for the same inputs. Base case: gcd(a, 0) = a; otherwise recurse on (b, a % b).
JavaScript
function gcdRecursive(a, 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)
);Explanation
The call stack mirrors the manual remainder sequence. Depth is O(log min(|a|,|b|)) in typical cases—still fine for interview-sized integers.
Applications
Fractions. Divide numerator and denominator by gcd to reduce p/q to lowest terms.
Modular inverses. When gcd(a,m)=1, an inverse of a modulo m exists (extended Euclid finds it).
Also: Chinese remainder setup, linear Diophantine solvability (ax+by=c iff gcd(a,b)|c), and RSA key generation (coprimality checks).
Binary gcd (Stein)
For very large integers, Stein’s algorithm trades division for shifts and subtraction; for plain Number, Euclidean code is already optimal in practice.
Interview: iterative Euclid is the default answer; mention extended gcd or binary gcd if the prompt goes deeper.
❓ FAQ
The greatest common divisor d of a and b is the largest positive integer that divides both a and b (when at least one is nonzero). Often written gcd(a,b) or (a,b).
For n > 0, gcd(0, n) = n because every positive divisor of n divides 0 as well. gcd(0, 0) is sometimes left undefined; many libraries return 0.
Repeatedly replace (a, b) with (b, a mod b) until b is 0. The gcd is then a—the last nonzero remainder from the previous step.
ES remainder matches truncated division toward zero: only magnitude fits Euclidean gcd cleanly unless you normalize. Reduce inputs with Math.abs (watch rare bigint/int boundaries in other languages).
It avoids expensive division on some hardware by using shifts and subtraction; asymptotics are similar for word-sized integers, but it is a useful alternative for very large integers in specialized libraries.
Euclid's algorithm on L-bit inputs takes O(L) arithmetic steps in the worst case (Lamé/Fibonacci bound); each step dominates at O(1) for fixed-width Number-safe integers.
🔄 Input / output examples
Change number1 and number2 in either program.
| (a, b) | gcd |
|---|---|
(48, 18) | 6 |
(17, 13) | 1 |
(0, 21) | 21 |
(12, 18) | 6 |
Edge cases and pitfalls
The loop while (num2 !== 0) assumes num2 eventually reaches zero; it always does for nonnegative inputs. With negatives, remainder signs can surprise you—normalize with Math.abs first.
Zero pair
gcd(0, 0)
The loop returns 0. Some definitions leave this undefined; document your convention in library code.
Sign
Negative inputs
Mathematical gcd is nonnegative. Normalize magnitudes before Euclid or verify against your spec.
MIN_SAFE
Number.MIN_SAFE_INTEGER
Math.abs works for safe integers; avoid mixing unsafe arithmetic when chaining many modular reductions.
Order
gcd(a,b)=gcd(b,a)
The Euclidean update tolerates either order after the first step.
⏱️ Time and space complexity
| Version | Time | Extra space |
|---|---|---|
| Iterative Euclid | O(log min(a,b)) steps (worst Fibonacci pair) | O(1) |
| Recursive Euclid | same | O(log min(a,b)) stack frames |
Lamé’s theorem bounds the number of division steps for inputs bounded by a fixed number of digits.
Summary
- Rule:
gcd(a,b)=gcd(b, a mod b)untilb=0; answer isa. - Code: compact loop or one-line recursion; both match the math.
- Watch-outs:
gcd(0,0), ES remainder with negatives, normalize magnitudes.
Did you know?
Bézout's identity: for integers a, b not both zero, there exist integers x, y with gcd(a,b) = a x + b y. The extended Euclidean algorithm finds such coefficients while computing the gcd.
About the author
8 people found this page helpful