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,Mathematics

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!

You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? *Contact-me*!

This page is using the new English version of dCode, *please make comments* !

Sponsored ads

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

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

Let the numbers be 10 and 12, one wants to find the GCD

10 has for divisors 1,2,5,10.

12 has for divisors 1,2,3,4,6,12.

The greatest common divisor is 2.

**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) until the remainder is zero.

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

12 / 10 = 1 remainder 2

10 / 2 = 5 remainder 0, the remainder is null

GCD(10, 12) = 2 the last remainder not null

**Method 3**: use prime factor decomposition

10 = 2 * 5

12 = 2 * 2 * 3

GCD is the multiplication of common factors

PGCD (10,12) = 2

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

Let the numbers be 10, 20 and 25, one wants to find the GCD

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.

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

GCD (10,20) = 10

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

**Method 3**: use prime factor decomposition

10 = 2 * 5

20 = 2 * 2 * 5

25 = 5 * 5

GCD is the multiplication of common factors

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

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.

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). By convention, only the positive value is given.

An alternative method to euclidean division uses successive subtractions based on the properties pgcd(a,b) = pgcd(b,a) = pgcd(b,a-b) = pgcd(a,b-a).

PGCD(12, 10) = PGCD(10, 12-10=2) = PGCD(2, 10-2=6) = PGCD(6, 6-2=4) = PGCD(4, 4-2=2) = PGCD(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);

}

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 q

However GCD(a,b) = a product of factors p

And GCD(a,c) = a product of factors q

And PGCD(a,b*c) = 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`"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`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

dCode retains ownership of the source code of the script GCD (Greatest Common Divisor). Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, etc.) which dCode owns rights can be transferred after sales quote. So if you need to download the GCD (Greatest Common Divisor) script for offline use, for you, your company or association, see you on contact page !

- How to calculate the GCD? (Algorithm)
- How to calculate the GCD with multiple numbers? (GCD of 3 numbers or more)
- What is the definition of two numbers relatively primes?
- 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)?

gcd,greatest,highest,common,divisor,multiple,algorithm,fraction,integer,division,euclidean,euclide

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

© 2017 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode