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

GCD (Greatest Common Divisor) - dCode

Tag(s) : Arithmetics

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*!

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

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

** 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(

__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

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

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.

`// 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} * 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) $

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

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 !

Please, check our community Discord for help requests!

- GCD of 2 or more numbers Calculator
- LCM Calculator
- List of Divisors
- What is the GCD? (Definition)
- How to calculate the GCD? (Algorithm)
- How to find the GCD with multiple numbers? (GCD of 3 numbers or more)
- What is the definition of two numbers relatively primes?
- What is the différence between GCD and HCF ?
- How to calculate GCD with negative integers?
- How to calculate GCD with subtractions?
- How to code GCD algorithm?
- How to demonstrate that if GCD(b,c)=1, then GCD(a,b*c) = GCD(a,b).GCD(a,c)
- How to calculate GCD with a calculator (TI or Casio)?
- What is the difference between GCD and LCM Calculator?

gcd,greatest,highest,common,divisor,algorithm,integer,division,euclidean,euclide,calculate

Source : https://www.dcode.fr/gcd

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲