Chapter 10: ufunc Finding GCD
1. What is GCD? (quick but important reminder)
The Greatest Common Divisor (also called Greatest Common Factor or Highest Common Factor) of two or more integers is the largest positive integer that divides all of them without leaving a remainder.
Examples:
- GCD(12, 18) = 6
- GCD(48, 60, 36) = 12
- GCD(7, 13) = 1 (coprime numbers)
- GCD(0, 0) = 0 (by convention in most libraries)
2. NumPy has built-in GCD support – since when?
Important timeline:
| Version | Has np.gcd? | Has np.gcd.reduce? | Recommendation |
|---|---|---|---|
| < 1.9 | No | No | You must implement it |
| 1.9 – 1.17 | Yes | No | Use np.gcd for pairs |
| ≥ 1.18 | Yes | Yes | Use np.gcd and np.gcd.reduce |
Today (2025) almost everyone is on 1.20+ or 2.x, so we can use the modern functions.
3. The two main GCD functions you need
| Function | What it does | Returns | Typical usage |
|---|---|---|---|
| np.gcd(a, b) | Element-wise GCD of two arrays (or scalars) | array or scalar | pairwise GCD |
| np.gcd.reduce(arr) | GCD of all elements in array (or along axis) | scalar or reduced array | GCD of many numbers |
4. Basic usage examples – scalars and pairs
|
0 1 2 3 4 5 6 7 8 9 10 |
print("GCD of 12 and 18:", np.gcd(12, 18)) # 6 print("GCD of 48 and 60:", np.gcd(48, 60)) # 12 print("GCD of 7 and 13:", np.gcd(7, 13)) # 1 print("GCD of 0 and 25:", np.gcd(0, 25)) # 25 print("GCD of 0 and 0:", np.gcd(0, 0)) # 0 |
Element-wise on arrays (very powerful)
|
0 1 2 3 4 5 6 7 8 9 10 |
a = np.array([12, 48, 7, 0, 30]) b = np.array([18, 60, 13, 25, 42]) print("Pairwise GCD:", np.gcd(a, b)) # [ 6 12 1 25 6] |
5. Finding GCD of many numbers – np.gcd.reduce
This is the most common real need.
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
numbers = np.array([12, 18, 24, 36, 48]) print("GCD of all:", np.gcd.reduce(numbers)) # 6 # More realistic example periods = np.array([12, 18, 30, 45, 60]) print("When do all cycles repeat together?", np.gcd.reduce(periods)) # 6 |
Along an axis (very useful with 2D data)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
matrix = np.array([ [12, 18, 24], [30, 45, 60], [36, 48, 72] ]) print("GCD of each column:", np.gcd.reduce(matrix, axis=0)) # [ 6 3 12] print("GCD of each row:", np.gcd.reduce(matrix, axis=1)) # [ 6 15 12] |
6. Realistic examples you will actually meet
Example 1 – Finding when multiple periodic events align again
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Three machines need service every 15, 24, and 40 days service_interval = np.array([15, 24, 40]) first_common_day = np.lcm.reduce(service_interval) # if you have lcm print("First common service day:", first_common_day) # 120 # But if we only have GCD for some reason (example) print("GCD of intervals:", np.gcd.reduce(service_interval)) # 1 |
Example 2 – Simplifying fractions (classic school problem)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
numerators = np.array([12, 18, 24, 36]) denominators = np.array([30, 45, 60, 72]) common_divisor = np.gcd(numerators, denominators) simplified_num = numerators // common_divisor simplified_den = denominators // common_divisor print("Original fractions:") for n, d in zip(numerators, denominators): print(f"{n}/{d}", end=" ") print("\nSimplified:") for n, d in zip(simplified_num, simplified_den): print(f"{n}/{d}", end=" ") |
Example 3 – Finding GCD of array elements along axis
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
# Measurements from 4 sensors over 100 time steps # Want GCD of readings per sensor (example scenario) readings = np.random.randint(10, 200, size=(100, 4)) * 5 # multiples of 5 gcd_per_sensor = np.gcd.reduce(readings, axis=0) print("GCD of all readings per sensor:", gcd_per_sensor) |
Example 4 – Batch GCD computation (very common in coding problems)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Multiple pairs at once pairs = np.array([ [12, 18], [48, 60], [7, 13], [100, 125], [0, 50] ]) print("GCD of each pair:") print(np.gcd(pairs[:,0], pairs[:,1])) # [ 6 12 1 25 50] |
7. Summary – NumPy GCD Quick Reference
| Situation | Best syntax (modern NumPy) |
|---|---|
| GCD of two numbers | np.gcd(a, b) |
| Pairwise GCD of two arrays | np.gcd(array1, array2) |
| GCD of many numbers (whole array) | np.gcd.reduce(array) |
| GCD along axis (rows/columns) | np.gcd.reduce(array, axis=0 or 1) |
| Older NumPy (before 1.18) | Implement with abs(a*b) // np.gcd(a,b) |
Final teacher advice (very important)
Golden rule #1 If your NumPy is 1.18 or newer → always use np.gcd and np.gcd.reduce — they are optimized and clean.
Golden rule #2 When you want GCD of more than two numbers, always use .reduce() — never write a loop.
Golden rule #3 GCD is always positive — NumPy returns positive values even if inputs are negative.
Golden rule #4 GCD(a, 0) = |a| GCD(0, 0) = 0 (by convention)
Golden rule #5 LCM and GCD are closely related:
|
0 1 2 3 4 5 6 |
lcm(a, b) = abs(a * b) // gcd(a, b) |
So if you have np.gcd, you can easily build LCM yourself.
Would you like to continue with any of these next?
- How to find LCM using GCD (very common follow-up)
- GCD of more than two numbers efficiently
- Common GCD coding competition patterns
- Realistic mini-project: fraction simplification or cycle alignment
- Handling very large numbers (when GCD is used in modular arithmetic)
Just tell me what you want to focus on next! 😊
