GCD (Greatest Common Divisor)

The GCD (for greater common divisor) of two integers is the largest natural integer is a divisor of these two integers.

GCD Method 1: list divisors of each number and find the greatest common divisor.

GCD Method 2: use Euclidean algorithm (prefered method for calculators)

Step 1. Make an euclidean division of the largest of the 2 numbers A by the other one B, to find a dividend D and a remainder R. Keep the numbers B and R.

Step 2. Repeat step 1 (with numbers kept, B becomes the new A and R becomes the new B) until the remainder is zero.

Step 3. GCD of A and B is equal to the last non zero remainder.

GCD Method 3: use prime factor decomposition

GCD is the multiplication of common factors (e.g. the product of all numbers presents in all decompositions).

GCD Method 4: knowing the GCD, use the formula GCD(a, b) = a * b / LCM(a, b)

GCD Method 1: list divisors of the numbers and find the greatest common divisor.

GCD Method 2: use the formula GCD(a,b,c) = GCD( GCD (a,b) , c )

GCD Method 3: use prime factor decomposition

GCD is the multiplication of common factors

To simplify a fraction, it is possible to divide the numerator and demonimator by their GCD to obtain an irreducible fraction.

Two numbers $ a $ and $ b $ are said to be relatively prime if there is no number except $ 1 $ which is both the divisor of $ a $ and $ b $.

Two numbers $ a $ and $ b $ are said to be co-prime if their GCD is $ 1 $: $ gcd(a,b) = 1 $

HCF stands for highest common factor, it is exactly the same thing as GCD.

The program ignores negative numbers. To be rigorous mathematically, it depends on the definition of PGCD, defined over N*, it is always positive, defined over Z* it can be negative, but it is the same, with a -1 coefficient. By convention, only the positive value is given. $$ GCD(a,b) = GCD(-a,b) = GCD(a,-b) = GCD(-a,-b) $$

An alternative method to euclidean divisions using successive subtractions based on the property $$ gcd(a,b) = gcd(b,a) = gcd(b,a-b) = gcd(a,b-a) $$

Use the formula $ GCD(a,b) = (a \times b) / LCM(a, b) $

with $ a \times b $ the product of the 2 numbers and LCM their least common multiple

// JAVASCRIPT
function pgcd(a,b) {
return (b==0)?a:pgcd(b,a%b);
}
// PHP
function pgcd($a,$b) {
return ($b==0)?$a:pgcd($b,$a%$b);
}
// Python
def gcd(a, b):
while b!=0:
a,b=b,a%b
return a


Using prime factor decomposition

$$ b = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n} $$

$$ c = q_1^{b_1} \times q_2^{b_2} \times \cdots \times q_m^{b_m} $$

As GCD(b,c)=1, no factor $ p $ is equal to any factor $ q $. However $ GCD(a,b) $ is a product of factors $ p $ and $ GCD(a,c) $ is a product of factors $ q $ and $ GCD(a, b \times c) $ is a product of factors $ p $ and $ q $. So $ GCD(a, b \times c) = GCD(a,b) \times GCD(a,c) $

Calculators has generally a function for GCD, else here are programs

For Casio
// GCD Finder
"A=" : ? -> R
"B=" : ? -> Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
WhileEnd
"U=" : U : "V=" : V
"PGCD=" : R

for TI (82,83,84,89)Input "A=", R
Input "B=", Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
End
Disp "U=", U, "V=3, V
Disp "PGCD=", R

The GCD is a common divisor (the greatest) of the 2 numbers, which is a smaller number having both numbers for multiples.

The LCM is a common multiple (the lowest) of the 2 numbers, which is a larger number having both numbers for divisors.

The CGD and the LCM are linked by the formula: $$ GCD(a, b) = \frac{ a \times b }{ LCM(a, b) } $$