Search for a tool
GCD (Greatest Common Divisor)

Tool to compute GCD. The greatest common divisor of two integers is the greatest positive integer which divides simultaneously these two integers.

Results

GCD (Greatest Common Divisor) -

Tag(s) : Arithmetics

Share
Share
dCode and you

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!


Please, check our community Discord for help requests!


Thanks to your feedback and relevant comments, dCode has developped the best GCD (Greatest Common Divisor) tool, so feel free to write! Thank you !

GCD (Greatest Common Divisor)

GCD of 2 or more numbers Calculator







List of Divisors

Tool to compute GCD. The greatest common divisor of two integers is the greatest positive integer which divides simultaneously these two integers.

Answers to Questions

What is the GCD? (Definition)

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

How to calculate the GCD? (Algorithm)

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

Example: GCD of the numbers 10 and 12.
10 has for divisors' list: 1,2,5,10
12 has for divisors' list: 1,2,3,4,6,12
The greatest common divisor (of these lists) is 2 (The largest number in all lists).
So, GCD(10,12) = 2

GCD Method 2: use Euclidean algorithm

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.

Example: A=12 and B=10, and (step 1) compute A/B = 12/10 = 1 remainder R=2.
(step 2) 10/2 = 5 remainder 0, the remainder is zero.
The last remainder not null is 2, so GCD(10, 12) = 2.

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).

Example: Numbers 10 and 12 which prime decomposition are: 10 = 2 * 5 and 12 = 2 * 2 * 3. The only common factor is 2. So GCD(10,12) = 2

How to find the GCD with multiple numbers? (GCD of 3 numbers or more)

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

Example: Search for the GCD of the numbers 10, 20 and 25.
10 has for divisors 1,2,5,10.
20 has for divisors 1,2,4,5,10,20.
25 has for divisors 1,5,25.
The greatest common divisor is 5.

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

Example: GCD (10,20) = 10

Example: GCD (10,20,25) = GCD( GCD(10,20), 25) = GCD(10, 25) = 5

GCD Method 3: use prime factor decomposition

Example: 10 = 2 * 5
20 = 2 * 2 * 5
25 = 5 * 5

GCD is the multiplication of common factors

Example: GCD (10,20,25) = 5

What is the definition of two numbers relatively primes?

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 $

What is the différence between GCD and HCF ?

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

How to calculate GCD with negative integers?

The program ignore 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. $$ PGCD(a,b) = PGCD(-a,b) = PGCD(a,-b) = PGCD(-a,-b) $$

Example: In this second case, for all solution, the opposite is valid: PGCD(6,9) = PGCD(-6,9) = PGCD(6,-9) = PGCD(-6,-9) = 3 (ou -3).

How to calculate GCD with subtractions?

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) $$

Example: GCD(12, 10) = GCD(10, 12-10=2) = GCD(2, 10-2=8) = GCD(8, 8-2=6) = GCD(6, 8-6=2) = GCD(6, 6-2=4) = GCD(4, 6-4=2) = GCD(4, 4-2=2) = GCD(2, 2) = 2.

How to code GCD algorithm?

// 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

How to demonstrate that if GCD(b,c)=1, then GCD(a,b*c) = GCD(a,b).GCD(a,c)

Using prime factor decomposition

$$ b = p_1^{a_1} * p_2^{a_2} * ... * p_n^{a_n} $$

$$ c = q_1^{b_1} * q_2^{b_2} * ... * 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 $ PGCD(a,b*c) $ is a product of factors $ p $ and $ q $. So $ PGCD(a,b*c) = PGCD(a,b) * PGCD(a,c) $

How to calculate GCD with a calculator (TI or Casio)?

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

What is the difference between GCD and LCM?

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)} $$

Source code

dCode retains ownership of the online 'GCD (Greatest Common Divisor)' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (PHP, Java, C#, Python, Javascript, Matlab, etc.) no data, script or API access will be for free, same for GCD (Greatest Common Divisor) download for offline use on PC, tablet, iPhone or Android !

Need Help ?

Please, check our community Discord for help requests!

Questions / Comments

Thanks to your feedback and relevant comments, dCode has developped the best GCD (Greatest Common Divisor) tool, so feel free to write! Thank you !


Source : https://www.dcode.fr/gcd
© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.
Feedback