Definition
Largest divisor
gcd(a, b) divides both; gcd = 1 means coprime.
Find GCD in PHP
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), lcm from gcd, a live preview, worked PHP 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.
LCM helper
Reuse gcd
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).
php
// 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 |
| LCM demo | intdiv(abs(ab), gcd) | Reuse your gcd helper |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Normalize | $a = abs($a); $b = abs($b); |
| Euclid step | [$a, $b] = [$b, $a % $b] |
| Stop | while ($b !== 0) then return $a |
| LCM | intdiv(abs($a * $b), gcd($a, $b)) |
| LCM | intdiv(abs($a * $b), gcd($a, $b)) |
| Classic | gcd(48, 18) = 6 |
Compare
📋 Iterative vs Recursive vs LCM
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
LCM
intdiv(abs(ab), g)Reuse gcd in app code
Interview tip
write EuclidThen mention GMP or 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 PHP programs — iterative Euclid, recursive Euclid, and an LCM demo. 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.
php
<?php
function findGcd(int $num1, int $num2): int
{
$num1 = abs($num1);
$num2 = abs($num2);
while ($num2 !== 0) {
[$num1, $num2] = [$num2, $num1 % $num2];
}
return $num1;
}
$number1 = 48;
$number2 = 18;
$g = findGcd($number1, $number2);
echo "GCD of $number1 and $number2 is: $g" . PHP_EOL;
?>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).
php
<?php
function gcdRecursive(int $a, int $b): int
{
$a = abs($a);
$b = abs($b);
if ($b === 0) {
return $a;
}
return gcdRecursive($b, $a % $b);
}
$number1 = 48;
$number2 = 18;
echo "GCD of $number1 and $number2 is: " . gcdRecursive($number1, $number2) . PHP_EOL;
?>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)).
⚙️ LCM Demo
Reuse gcd to compute lcm with |ab|/gcd.
Example 3 — GCD Helper and LCM
Reusable gcd helper plus the classic LCM identity.
php
<?php
function gcd(int $a, int $b): int
{
$a = abs($a);
$b = abs($b);
while ($b !== 0) {
[$a, $b] = [$b, $a % $b];
}
return $a;
}
function lcm(int $a, int $b): int
{
if ($a === 0 || $b === 0) {
return 0;
}
return intdiv(abs($a * $b), gcd($a, $b));
}
foreach ([[48, 18], [17, 13], [0, 21], [-12, 18]] as [$a, $b]) {
$g = gcd($a, $b);
echo "gcd($a, $b) = $g, lcm = " . lcm($a, $b) . PHP_EOL;
}
?>How It Works
Prefer a tested gcd helper in real projects (normalize with abs first). In interviews, write Euclid yourself first, then mention GMP if needed 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: intdiv(abs(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 lcm/GMP 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.
→ Watch integer overflow on large products; use intdiv and abs carefully.
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
Large integers can overflow; GMP helps for big values.
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 |
| LCM demo | 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 reuse gcd for lcm 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 lcm and GMP
❌ 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
LCM
lcm demo
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.
No standard gcd function. Write Euclid in interviews; mention GMP (gmp_gcd) for very large values when the extension is available.
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