The least common multiple (LCM) of two integers is the smallest positive number that is divisible by both.
Remember
lcm(a, b) = smallest positive m such that
m % a == 0 and m % b == 0
Identity (nonnegative a, b):
gcd(a, b) × lcm(a, b) = a × b
⇒ lcm(a, b) = |a × b| / gcd(a, b)
Example: a = 12, b = 18
Multiples of 12: 12, 24, 36, 48, …
Multiples of 18: 18, 36, 54, …
First shared = 36
Check: gcd(12, 18) = 6 → 12 × 18 / 6 = 36
a
b
gcd
lcm
12
18
6
36
7
5
1
35
0
15
15
0
Approach
How to Find LCM in Python
Four clear steps — prefer the GCD formula in interviews and real code.
Take absolute values so negatives do not change the LCM.
If either value is 0, return 0.
Compute gcd(a, b) with Euclid’s algorithm (or math.gcd).
Return abs(a // gcd * b) (divide before multiply — good habit).
Method
Idea
Time
Best for
GCD formula
abs(a // gcd * b)
O(log min)
Interviews, production
Multiple scan
Increase by max(a, b) until both divide
O(lcm / max)
Teaching the definition
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):
a = abs(a), b = abs(b)
if a == 0 or b == 0:
return 0
g = Gcd(a, b)
return (a / g) * b
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Meaning
Smallest positive multiple of both
Formula
lcm = abs(a * b) // gcd(a, b)
Safe order
abs(a // gcd * b) — divide first
Zero
lcm(0, n) = 0
Built-in
math.lcm(a, b) (Python 3.9+)
Three numbers
lcm(lcm(a, b), c)
Classic check
lcm(12, 18) = 36
Try it
Live Preview
Enter two integers to see their GCD and LCM.
Whole numbers (absolute values used). Tap a chip or type a pair.
Result
a = 12, b = 18
gcd(12, 18) = 6
lcm = |12 × 18| / 6 = 36
Start with the GCD formula — fast and interview-ready. Use the multiple scan when you want to show the definition directly.
Example 1 — GCD Formula
Compute Euclid’s GCD, then return abs(a // gcd * b).
python
def gcd(a: int, b: int) -> int:
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
def lcm(a: int, b: int) -> int:
a, b = abs(a), abs(b)
if a == 0 or b == 0:
return 0
return a // gcd(a, b) * b
print(f"LCM = {lcm(12, 18)}")
Output
LCM = 36
How It Works
Take absolute values so sign does not matter.
If either side is 0, return 0.
gcd repeats a % b until the remainder is 0.
For 12 and 18, gcd is 6.
12 // 6 * 18 = 36 — divide first. Shortcut in real code: math.lcm(12, 18).
Example 2 — Multiple Scan
Start from the larger number and step by that size until both divide evenly.
python
def lcm(a: int, b: int) -> int:
a, b = abs(a), abs(b)
if a == 0 or b == 0:
return 0
step = max(a, b)
candidate = step
while True:
if candidate % a == 0 and candidate % b == 0:
return candidate
candidate += step
print(lcm(12, 18)) # 36
print(lcm(7, 5)) # 35
Output
36
35
How It Works
Handle zeros and absolute values like Example 1.
Set step = max(a, b) — the LCM cannot be smaller than that.
Test candidate; if both divide it, you found the LCM.
Otherwise add step and try again.
Clear for teaching, but slower than the GCD formula for large values.
Edge Cases & Pitfalls
Check these before calling the solution done.
Zero
lcm(0, n) = 0
Return early so you never divide by a zero GCD path incorrectly.
Order
Divide first
Prefer a // gcd * b. Python ints grow freely, but the habit matters in interviews and other languages.
Negatives
Use abs()
LCM is usually reported as a nonnegative value.
Coprime
gcd = 1
Then lcm(a, b) = abs(a * b) — still correct.
Analysis
Time and Space Complexity
Program
Time
Extra space
GCD formula
O(log min(a, b))
O(1)
Multiple scan
O(lcm / max(a, b))
O(1)
Euclid’s GCD dominates the formula method. The scan walks multiples until it hits the LCM.
Remember
Key Takeaways
Definition: smallest positive number divisible by both inputs.
Formula:lcm = abs(a * b) // gcd(a, b).
Safety:a // gcd * b; built-in math.lcm for real projects.
