The GCD (greatest common divisor), also called HCF, is the largest positive integer that divides both numbers.
Remember
gcd(a, b) = largest positive d such that
a % d == 0 and b % d == 0
Euclid:
while b != 0:
(a, b) = (b, a % b)
return a
Example: gcd(48, 18)
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
gcd = 6
a
b
gcd
48
18
6
17
13
1
0
21
21
Approach
How to Find GCD in C
Four clear steps — Euclid’s algorithm is the standard interview answer.
Take absolute values so negatives do not change the GCD.
While b != 0, replace (a, b) with (b, a % b).
When b becomes 0, return a.
Handle gcd(0, 0) as your problem requires (often return 0).
Method
Idea
Time
Best for
Iterative Euclid
Loop with a % b until b == 0
O(log min)
Interviews, production
Recursive Euclid
gcd(b, a % b) with base b == 0
O(log min)
Showing the recurrence
Pseudocode
Pseudocode
function Gcd(a, b):
a = abs(a)
b = abs(b)
while b != 0:
t = b
b = a mod b
a = t
return a
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Meaning
Largest positive common divisor
Also called
HCF
Core step
(a, b) → (b, a % b)
Stop when
b == 0; answer is a
Zero
gcd(0, n) = |n| for n ≠ 0
Classic check
gcd(48, 18) = 6
Try it
Live Preview
Enter two integers to see the Euclidean steps and the GCD.
Whole numbers (absolute values used). Tap a chip or type a pair.
Start with the iterative Euclidean loop. Use recursion when you want to show the recurrence clearly.
Example 1 — Iterative Euclid
Loop with remainder until b becomes zero, then return a.
C
#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
int t;
a = abs(a);
b = abs(b);
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
int main(void)
{
printf("GCD = %d\\n", gcd(48, 18));
return 0;
}
Output
GCD = 6
How It Works
Take absolute values so sign does not matter.
While b != 0, save b in t.
Set b = a % b (new remainder) and a = t.
When b hits 0, a holds the GCD.
For 48 and 18 the remainders are 12, then 6, then 0 → answer 6.
Example 2 — Recursive Euclid
Same algorithm as a one-line recurrence with a clear base case.
C
#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
a = abs(a);
b = abs(b);
if (b == 0)
{
return a;
}
return gcd(b, a % b);
}
int main(void)
{
printf("%d\\n", gcd(48, 18)); /* 6 */
printf("%d\\n", gcd(0, 21)); /* 21 */
printf("%d\\n", gcd(17, 13)); /* 1 */
return 0;
}
Output
6
21
1
How It Works
Normalize with abs first.
Base case: if b == 0, return a.
Otherwise call gcd(b, a % b).
Each call shrinks the problem — same steps as the loop.
Stack depth is O(log min(a, b)); prefer the loop in production.
Edge Cases & Pitfalls
Check these before calling the solution done.
Zero
gcd(0, n) = |n|
The loop ends immediately when the other value is already 0.
Negatives
Use abs
GCD is reported as a nonnegative value.
Coprime
gcd = 1
No larger common divisor — still a correct result.
% operator
Remainder, not divide
Euclid needs a % b, not floating-point division.
Analysis
Time and Space Complexity
Program
Time
Extra space
Iterative Euclid
O(log min(a, b))
O(1)
Recursive Euclid
O(log min(a, b))
O(log min) stack
Each remainder step shrinks the numbers quickly. That is why Euclid is much faster than scanning every candidate divisor.
Remember
Key Takeaways
Definition: largest positive integer that divides both inputs.
Euclid: replace with (b, a % b) until b == 0.
Alias: GCD = HCF.
Test: (48, 18) → 6; (17, 13) → 1; (0, 21) → 21.
One line: keep taking remainders until one side is zero — that other side is the GCD.
Frequently Asked Questions
The greatest common divisor (also called HCF) of a and b is the largest positive integer that divides both.
For n > 0, gcd(0, n) = n. Many programs treat gcd(0, 0) as 0.
Replace (a, b) with (b, a % b) until b becomes 0. Then a is the GCD.
Same idea. Iteration uses O(1) extra space; recursion uses O(log min(a,b)) stack frames.
For nonnegative a and b: gcd(a, b) × lcm(a, b) = a × b (when neither is zero in the usual product form).
