18x48 6
- Idea
- largest common square size
Find GCD in PHP
What you’ll learn
- The definition of gcd(
a,b) and the casegcd(0, n) = |n|. - Euclidean algorithm in iterative and recursive PHP forms.
- How gcd helps in fraction reduction, coprime checks, and number theory problems.
Overview
Euclid’s rule gcd(a,b) = gcd(b, a % b) reduces values quickly until remainder becomes zero.
Two programs
Iterative and recursive Euclid for 48 and 18.
Live preview
Try two values and see gcd instantly.
Rigor
Covers zero and sign normalization clearly.
Prerequisites
Integer division, remainder (%), loops, and basic PHP functions.
- Understand how
%gives remainder. - Know that we usually report gcd as a nonnegative number.
What is gcd?
gcd(a,b) is the largest positive integer that divides both a and b.
If gcd(a,b)=1, the numbers are called coprime.
48, 18 gcd = 6
Euclid gcd(a,b)=gcd(b,a%b)
LCM link |ab|/gcd
Reduction step
Euclid uses gcd(a,b) = gcd(b, a mod b) when b != 0.
gcd(48, 18)gcd(48,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.
Live preview
Safe integers only. Negative inputs are normalized by magnitude.
Algorithm
Goal: compute gcd(a,b) for integers.
Normalize
Use absolute values if you want nonnegative gcd.
Loop
While b != 0, set (a,b) = (b, a % b). Return a.
📜 Pseudocode
Pseudocode
function gcd(a, b):
while b != 0:
(a, b) = (b, a mod b)
return a1
Iterative Euclidean algorithm
Classic loop version for two numbers.
php
<?php
function findGcd(int $num1, int $num2): int
{
$num1 = abs($num1);
$num2 = abs($num2);
while ($num2 !== 0) {
$temp = $num2;
$num2 = $num1 % $num2;
$num1 = $temp;
}
return $num1;
}
$number1 = 48;
$number2 = 18;
$g = findGcd($number1, $number2);
echo "GCD of {$number1} and {$number2} is: {$g}\n";
?>Explanation
Each step moves old b into a and replaces b by remainder a % b. Final nonzero value is gcd.
2
Recursive Euclidean algorithm
Compact recursive style with base case b = 0.
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) . "\n";
?>Explanation
Recursive calls follow same remainder chain as the iterative version.
Applications
Fractions. Reduce p/q by dividing both by gcd.
Coprime check. gcd(a,b)=1 means the pair is coprime.
Also: modular inverse checks, Diophantine equations, and CRT prep.
Binary gcd (Stein)
Binary gcd uses shifts/subtractions. Euclid remains the simplest interview answer.
Interview: write iterative Euclid first; mention advanced variants only if asked.
❓ 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).
For n > 0, gcd(0, n) = n. For gcd(0,0), many implementations return 0 by convention.
Repeatedly replace (a, b) with (b, a mod b) until b becomes 0. The gcd is then a.
Mathematical gcd is usually nonnegative. In practice, normalize with absolute values first.
It uses shifts/subtractions instead of division. Euclid is still the standard interview answer.
Euclid runs in O(log min(a,b)) steps for positive inputs.
🔄 Input / output examples
Change the two input numbers in either example.
| (a, b) | gcd |
|---|---|
(48, 18) | 6 |
(17, 13) | 1 |
(0, 21) | 21 |
(12, 18) | 6 |
Edge cases and pitfalls
Normalize signs and define behavior for gcd(0,0) clearly in your project.
Zero pair
gcd(0, 0)
Often returned as 0 by convention.
Sign
Negative inputs
Apply abs() first for nonnegative gcd output.
Order
gcd(a,b)=gcd(b,a)
Input order does not change final gcd.
⏱️ 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 |
Summary
- Rule: keep applying
(a,b)=(b,a%b)untilb=0. - Code: iterative and recursive forms are both simple and standard.
- Watch-outs: sign normalization and
gcd(0,0)convention.
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