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

dCode and you

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!


Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best GCD (Greatest Common Divisor) tool. Thank you.

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

GCD (Greatest Common Divisor)

Sponsored ads

This script has been updated, please report any problems.

Calculus of GCP of any numbers



List of Divisors

Also on dCode: Divisors of a Number

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

How to calculate the GCD? (Algorithm)

Method 1: list divisorshref 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 divisorshref 1,2,5,10.

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

The greatest common divisor is 2.

Method 2: use Euclidean algorithm

Step 1. Make an euclidean divisionhref 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 factorhref decomposition

10 = 2 * 5

12 = 2 * 2 * 3

GCD is the multiplicationhref of common factors

PGCD (10,12) = 2

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

Method 1: list divisorshref 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 divisorshref 1,2,5,10.

20 has for divisorshref 1,2,4,5,10,20.

25 has for divisorshref 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 factorhref decomposition

10 = 2 * 5

20 = 2 * 2 * 5

25 = 5 * 5

GCD is the multiplicationhref of common factors

GCD (10,20,25) = 5

What is the definition of two numbers relatively primes?

Two numbers are relatively primes if their PGCD is 1.

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.

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.

How to calculate GCD with subtractions?

An alternative method to euclidean divisionhref 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.

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

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

Using prime factorhref 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)

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

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 TIInput "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

Ask a new question

Source code

dCode retains ownership of the source code of the script GCD (Greatest Common Divisor). Except explicit open source licence (free / freeware), any algorithm, applet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any snippet or function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in PHP (or 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 !

Questions / Comments


Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best GCD (Greatest Common Divisor) tool. Thank you.


Source : http://www.dcode.fr/gcd
© 2016 dCode — The ultimate 'toolkit' website to solve every problem. dCode