18 x 486
- Tile idea
- largest equal square side
Find GCD in Python
What you’ll learn
- Definition of gcd(a,b) and
gcd(0,n)=|n|. - Euclidean algorithm in iterative and recursive Python forms.
- Applications like fraction reduction and modular arithmetic basics.
Overview
Euclid’s rule gcd(a,b)=gcd(b,a%b) reduces numbers quickly. When remainder becomes zero, the current value is the gcd.
Two programs
Iterative and recursive Euclid for 48 and 18.
Live preview
Interactive gcd computation with safe integer checks.
Rigor
Covers gcd(0,0) convention and negative inputs.
Prerequisites
Remainder operator %, loops, and functions.
- Use
abs()for sign normalization. - Understand loop invariant ideas: gcd stays same under Euclid step.
What is gcd?
gcd(a,b) is the largest positive integer dividing both numbers.
If gcd is 1, numbers are coprime. Also, lcm(a,b) = |ab| / gcd(a,b) for nonzero pairs.
48, 18gcd = 6
Euclidgcd(a,b)=gcd(b,a%b)
Coprimegcd = 1
Reduction step
gcd(a,b)=gcd(b,a%b) because common divisors are preserved when replacing a by remainder modulo b.
gcd(48,18)gcd(48,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6
Intuition
18/483/8
- Reduce
- divide by gcd 6
Takeaway: gcd is the last nonzero value in the Euclidean remainder chain.
Live preview
Enter two integers (safe range). We compute gcd on magnitudes.
Algorithm
Goal: compute gcd(a,b) for integers.
Normalize
Use a = abs(a), b = abs(b).
Euclidean loop
While b != 0, do a, b = b, a % b. Return a.
📜 Pseudocode
Pseudocode
function gcd(a, b):
a = abs(a)
b = abs(b)
while b != 0:
(a, b) = (b, a mod b)
return a1
Iterative Euclidean algorithm
Uses a loop to compute gcd for 48 and 18.
python
def find_gcd(num1: int, num2: int) -> int:
num1, num2 = abs(num1), abs(num2)
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
number1 = 48
number2 = 18
g = find_gcd(number1, number2)
print(f"GCD of {number1} and {number2} is: {g}")Explanation
Each loop step keeps gcd unchanged and reduces the second value until it becomes zero.
2
Recursive Euclidean algorithm
Base case b == 0; otherwise recurse on (b, a % b).
python
def gcd_recursive(a: int, b: int) -> int:
a, b = abs(a), abs(b)
if b == 0:
return a
return gcd_recursive(b, a % b)
number1 = 48
number2 = 18
print(f"GCD of {number1} and {number2} is: {gcd_recursive(number1, number2)}")Explanation
Recursive calls follow the same remainder chain as iterative Euclid, then return the final nonzero value.
Applications
Fractions: reduce p/q by dividing both by gcd.
Mod arithmetic: inverse of a (mod m) exists when gcd(a,m)=1.
Also: Diophantine equations, CRT setup, and coprime checks.
Binary gcd (Stein)
Alternative method using shifts/subtractions; Euclid is still the default interview answer.
Interview: mention binary gcd only if asked for alternatives.
❓ FAQ
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.
🔄 Input / output examples
Change number1 and number2 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) explicitly.
Zero pair
gcd(0,0)
Many implementations return 0 by convention.
Sign
Negative inputs
Use absolute values to keep gcd nonnegative.
Order
gcd(a,b)=gcd(b,a)
Input order does not change the answer.
Huge ints
Big integers
Python supports them, but runtime grows with digit length.
⏱️ 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 |
Worst-case step count appears on consecutive Fibonacci inputs.
Summary
- Rule:
gcd(a,b)=gcd(b,a%b)untilb=0. - Code: iterative and recursive versions both match the math.
- Watch-outs: define
gcd(0,0)and normalize sign.
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.
About the author
8 people found this page helpful