GCD (Greatest Common Divisor)
Last modified: 2023-08-29
The greatest common divisor is the largest number that divide two integers without a remainder. The Euclidean Algorithm is commonly used for computing GCD.
The following examples calculate the greatest common divisor of two given integers. Using
gcd method of
math in Python, we can easily compute GCD.
import math math.gcd(2, 8) # result: 2 math.gcd(5, 15) # result: 5 math.gcd(28, 72) # result: 4
The following snippet shows how the GCD works with the last example above (
# Calculate a remainder of 72/28 72 % 28 = 16 # Calculate a remainder using the previous number 16 28 % 16 = 12 # Repeat... 16 % 12 = 4 12 % 4 = 0
We got the decimal 4 before the final result is zero. This is the greatest common remainder.
The Extended Euclidean Algorithm finds integer coefficients
y as such that below, if we have values of
a * x + b * y = gcd(a, b)
The following Python script is an example to find the coefficients.
It refers to this article.
def egcd(a, b): if a == 0: return b, 0, 1 gcd, x1, y1 = egcd(b % a, a) x = y1 - (b//a) * x1 y = x1 return gcd, x, y # example values given a = 25031 b = 39125 print(egcd(a, b))
If all numbers given are primes, the following principle holds.
a = 2 b = 3 c = 5 gcd(a*b, a*c) # 2 (a) gcd(b*a, b*c) # 3 (b) gcd(c*a, c*b) # 5 (c)