The GCD (Greatest Common Divisor), also called HCF, is the largest positive integer that divides both numbers with no remainder.
Remember
gcd(a, b) = largest d > 0 such that
a % d == 0 and b % d == 0
Example: gcd(48, 18) = 6
48 = 6 * 8
18 = 6 * 3
No larger positive integer divides both
a
b
gcd(a, b)
48
18
6
17
13
1
0
21
21
-12
18
6
Approach
How to Find GCD in Python
Four clear steps — Euclid’s remainder loop is the interview default.
Take absolute values of a and b so the result is nonnegative.
While b != 0, replace (a, b) with (b, a % b).
When b becomes 0, return a — that is the GCD.
Optionally derive LCM with abs(a // gcd * b), or use math.gcd in real code.
Method
Idea
Time
Best for
Iterative Euclid
Loop with a % b until b == 0
O(log min)
Interviews, production default
Recursive Euclid
gcd(b, a % b) until base case
O(log min)
Showing the recurrence
LCM via GCD
abs(a // g * b)
O(log min)
Follow-up questions
Pseudocode
Pseudocode
function gcd(a, b):
a = abs(a)
b = abs(b)
while b != 0:
a, b = b, a mod b
return a
function lcm(a, b):
if a == 0 or b == 0:
return 0
return abs(a // gcd(a, b) * b)
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Core step
a, b = b, a % b
Stop when
b == 0; answer is a
Signs
Use abs() first
gcd(0, n)
abs(n) for n != 0
gcd(0, 0)
Usually defined as 0
Builtin
math.gcd(a, b)
LCM link
abs(a // g * b)
Classic check
gcd(48, 18) = 6
Try it
Live Preview
Enter two integers to see the Euclidean remainder chain and the GCD.
Start with the iterative loop — it is the clearest interview answer. Then show the recursive form, and finish with LCM built from GCD.
Example 1 — Iterative Euclidean Algorithm
Loop with remainders until the second value becomes zero.
python
def find_gcd(a, b):
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
number1 = 48
number2 = 18
print(f"GCD of {number1} and {number2} is: {find_gcd(number1, number2)}")
Output
GCD of 48 and 18 is: 6
How It Works
Take absolute values so negatives do not break the remainder chain.
While b != 0, swap with a remainder: a, b = b, a % b.
For (48, 18) the pairs become (18, 12), (12, 6), then (6, 0).
When b is 0, return a — here 6.
Extra space is O(1); time is logarithmic in the smaller number.
Example 2 — Recursive Euclidean Algorithm
Same remainder idea, written as a recurrence with a clear base case.
python
def find_gcd(a, b):
a, b = abs(a), abs(b)
if b == 0:
return a
return find_gcd(b, a % b)
number1 = 48
number2 = 18
print(f"GCD of {number1} and {number2} is: {find_gcd(number1, number2)}")
Same answer as the loop; stack depth is about O(log min(a, b)).
Prefer the iterative version when you must mention space carefully.
Example 3 — LCM via GCD
Use the identity lcm(a, b) = abs(a // gcd * b) after finding the GCD.
python
def find_gcd(a, b):
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
def find_lcm(a, b):
if a == 0 or b == 0:
return 0
g = find_gcd(a, b)
return abs(a // g * b)
a = 48
b = 18
print(f"gcd = {find_gcd(a, b)}")
print(f"lcm = {find_lcm(a, b)}")
Output
gcd = 6
lcm = 144
How It Works
Reuse the same iterative find_gcd helper.
If either input is 0, LCM is defined as 0 here.
Divide by the GCD first: a // g * b keeps intermediates smaller.
abs(...) keeps the LCM nonnegative for negative inputs.
