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

dCode retains ownership of the source code of the script GCD (Greatest Common Divisor) online. 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, Matlab, etc.) which dCode owns rights will not be released for free. To download the online GCD (Greatest Common Divisor) script for offline use on PC, iPhone or Android, ask for price quote on contact page !

- GCD of 2 or more numbers 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)?

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

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

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

Feedback

▲