📏 NumPy ufunc Finding GCD – Compute Greatest Common Divisors Efficiently

🧲 Introduction – Why Use NumPy GCD ufuncs?

The Greatest Common Divisor (GCD) is foundational in number theory, cryptography, rational simplification, and computational math. NumPy’s np.gcd() universal function (ufunc) offers a fast, element-wise way to compute GCDs on arrays of any shape, with support for broadcasting and array-wide reductions.

🎯 By the end of this guide, you’ll:

• Compute GCD using np.gcd() between scalars, vectors, and matrices
• Apply np.gcd.reduce() for GCD across an entire array
• Use broadcasting to pair scalars with arrays
• Combine with np.lcm() for integer-based computations

---

🔢 Step 1: Basic Element-wise GCD with np.gcd()

import numpy as np

a = np.array([12, 20, 100])
b = np.array([8, 30, 25])

print(np.gcd(a, b))

👉 Output:

[ 4 10 25]

🔍 Explanation:

• GCD(12, 8) = 4
• GCD(20, 30) = 10
• GCD(100, 25) = 25
  ✅ Element-wise computation

---

🔁 Step 2: GCD with Scalars and Arrays (Broadcasting)

arr = np.array([10, 15, 25])
print(np.gcd(arr, 5))  # [5 5 5]

🔍 Explanation:

• NumPy broadcasts scalar 5 across the array
  ✅ GCD calculated between 5 and each array element

---

🧮 Step 3: 2D GCD Example

A = np.array([[18, 24], [40, 100]])
B = np.array([[6, 36], [10, 50]])

print(np.gcd(A, B))

👉 Output:

[[ 6 12]
 [10 50]]

✅ Applies GCD computation element-wise to matrices

---

🔄 Step 4: GCD Across an Array with np.gcd.reduce()

arr = np.array([60, 48, 36])
print(np.gcd.reduce(arr))  # Output: 12

🔍 Explanation:

• GCD(60, 48) = 12 → GCD(12, 36) = 12
  ✅ gcd.reduce() applies pairwise reduction over the array

---

🔗 Step 5: Combine GCD with LCM

a, b = 12, 18
g = np.gcd(a, b)
l = np.lcm(a, b)

print(f"GCD: {g}, LCM: {l}")

👉 Output:

GCD: 6, LCM: 36

📌 Remember: LCM(a,b)=∣a×b∣GCD(a,b)\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}

---

⚠️ Notes and Edge Cases

Scenario	Behavior
np.gcd(0, n)	Returns `
Negative values	Allowed (returns absolute GCD)
Floating-point inputs	❌ Not allowed – only integers
Mixed types	Cast to integers automatically

---

📦 Bonus: Build a GCD Table (Matrix)

x = np.arange(1, 6).reshape(-1, 1)
y = np.arange(1, 6)

gcd_table = np.gcd(x, y)
print(gcd_table)

👉 Output:

[[1 1 1 1 1]
 [1 2 1 2 1]
 [1 1 3 1 1]
 [1 2 1 4 1]
 [1 1 1 1 5]]

✅ Creates a full pairwise GCD lookup table from 1 to 5 × 1 to 5

---

📌 Summary – Recap & Next Steps

NumPy’s gcd() ufunc gives you a high-performance, vectorized way to compute greatest common divisors, supporting arrays, scalars, broadcasting, and reduction.

🔍 Key Takeaways:

• Use np.gcd(a, b) for element-wise GCD
• Use np.gcd.reduce() for GCD across an array
• Supports broadcasting and multi-dimensional inputs
• Combine with np.lcm() for complete integer operations
• Only works with integer inputs (not float)

⚙️ Real-world relevance: Used in math modeling, cryptography, simplification of ratios, and modular systems

---

❓ FAQs – NumPy GCD ufunc

❓ Can I compute GCD of negative numbers?
✅ Yes. The result is always non-negative.

❓ Does NumPy GCD work with floats?
❌ No. Use integers only. Convert with astype(int) if needed.

❓ How do I find GCD of more than 2 numbers?
✅ Use np.gcd.reduce(array).

❓ What if I pass zero?
✅ np.gcd(0, n) returns |n|, as per math definition.

❓ Is there a NumPy version for math.gcd()?
✅ Yes. np.gcd() is vectorized and works across arrays.

---

Share Now :