Difference between revisions of "Greatest common divisor"
m |
|||
| Line 1: | Line 1: | ||
| − | The '''greatest common divisor''' ('''GCD''') of two [[integers]] | + | 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 | + | The GCD is sometimes called the '''greatest common factor''' ('''GCF'''). |
| + | The greatest common divisor of several numbers is divisible by any other common divisor of these numbers. | ||
| − | The GCD can be found in several ways. The first way invlolves factoring both numbers, and the second way uses | + | The GCD can be found in several ways. The first way invlolves factoring both numbers, and the second way uses [[Euclidean algorithm]]. |
---- | ---- | ||
| − | Once the prime | + | 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: | ||
| Line 25: | Line 26: | ||
---- | ---- | ||
| − | + | 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 <math>GCD(a_1,\dots,a_n)=GCD(GCD(a_1,dots,a_{n-1}),a_n)</math>. | |
For two numbers, a and b, the GCD can be at most |a-b|. Also, the GCD can also be no more than the difference in the largest multiple of the smaller number that is less than the larger number. By subtracting the largest multiple of the smaller number from the larger number over and over until the numbers are equal, you will end up with the largest number they both divide, the GCD. | For two numbers, a and b, the GCD can be at most |a-b|. Also, the GCD can also be no more than the difference in the largest multiple of the smaller number that is less than the larger number. By subtracting the largest multiple of the smaller number from the larger number over and over until the numbers are equal, you will end up with the largest number they both divide, the GCD. | ||
Revision as of 21:33, 18 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).
The greatest common divisor of several numbers is divisible by any other common divisor of these numbers.
The GCD can be found in several ways. The first way invlolves factoring both 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:
The common factors are 2 and 
, so the GCD is 
Another Example:
The common factors are 
and 3, making the GCD 
.
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 
.
For two numbers, a and b, the GCD can be at most |a-b|. Also, the GCD can also be no more than the difference in the largest multiple of the smaller number that is less than the larger number. By subtracting the largest multiple of the smaller number from the larger number over and over until the numbers are equal, you will end up with the largest number they both divide, the GCD.
Example: (1440, 560) (1440, 1120) (320, 1120) (960, 1120) (160, 960) (160, 160), so the GCD is 160.
Another Example: (1200, 720, 288) (1200, 720, 576) (624, 144, 576) (624, 576, 576) (624, 576) (48, 576) (48, 48), so the GCD is 48.
