Difference between revisions of "Greatest common divisor"

m (proofreading)
Line 1: Line 1:
The '''greatest common divisor''' ('''GCD''') of two or more [[integers]] is the largest integer that is a [[divisor]] of all the given numbers
+
The '''greatest common divisor''' ('''GCD''') of two or more [[integers]] is the largest integer that is a [[divisor]] of all the given numbers.
  
 
The GCD is sometimes called the '''greatest common factor''' ('''GCF''').
 
The GCD is sometimes called the '''greatest common factor''' ('''GCF''').
Line 7: Line 7:
  
  
The GCD can be found in two ways.  The first way invlolves factoring the numbers, and the second way uses [[Euclidean algorithm]].
+
The GCD can be found in two ways.  The first way involves factoring the numbers, and the second way uses [[Euclidean algorithm]].
  
 
----
 
----
Line 13: Line 13:
 
Once the prime factorizations of the given numbers has been found, the greatest common divisor is the product of all common factors of the numbers.
 
Once the prime factorizations of the given numbers has been found, the greatest common divisor is the product of all common factors of the numbers.
  
Example:
+
Example:<br>
<math>270=2\times3^3\times5</math>
+
<math>270=2\times3^3\times5</math><br>
 
<math>144=2^4\times3^2</math>
 
<math>144=2^4\times3^2</math>
  
 
The common factors are 2 and <math>3^2</math>, so the GCD is <math>2\times3^2=18</math>
 
The common factors are 2 and <math>3^2</math>, so the GCD is <math>2\times3^2=18</math>
  
Another Example:
+
Another Example:<br>
<math>1200=2^4\times3\times5</math>
+
<math>1200=2^4\times3\times5</math><br>
<math>720=2^4\times3^2\times5</math>
+
<math>720=2^4\times3^2\times5</math><br>
 
<math>288=2^5\times3^2</math>
 
<math>288=2^5\times3^2</math>
  

Revision as of 13:35, 19 June 2006

The greatest common divisor (GCD) of two or more integers is the largest integer that is a divisor of all the given numbers.

The GCD is sometimes called the greatest common factor (GCF).

A very useful property of the GCD is that it can be represented as a sum of the given numbers with integer coefficients. From here it immediately follows that the greatest common divisor of several numbers is divisible by any other common divisor of these numbers.


The GCD can be found in two ways. The first way involves factoring the numbers, and the second way uses Euclidean algorithm.


Once the prime factorizations of the given numbers has been found, the greatest common divisor is the product of all common factors of the numbers.

Example:
$270=2\times3^3\times5$
$144=2^4\times3^2$

The common factors are 2 and $3^2$, so the GCD is $2\times3^2=18$

Another Example:
$1200=2^4\times3\times5$
$720=2^4\times3^2\times5$
$288=2^5\times3^2$

The common factors are $2^4$ and 3, making the GCD ${2^4\times3=48}$.


The Euclidean Algorithm is much faster and can be used to give the GCD of any two numbers without knowing their prime factorizations. To find the greatest common divisor of more than two numbers, one can use the recursive formula $\displaystyle GCD(a_1,\dots,a_n)=GCD(GCD(a_1,\dots,a_{n-1}),a_n)$.