Difference between revisions of "Greatest common divisor"
(→binary method) |
|||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| + | This video comprehensively explains everything related to the GCD: https://youtu.be/HboSeb_gQH8 | ||
The '''greatest common divisor''' ('''GCD''', or '''GCF''' ('''greatest common factor''')) of two or more [[integer]]s is the largest integer that is a [[divisor]] of all the given numbers. | The '''greatest common divisor''' ('''GCD''', or '''GCF''' ('''greatest common factor''')) of two or more [[integer]]s is the largest integer that is a [[divisor]] of all the given numbers. | ||
| Line 5: | Line 6: | ||
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. | 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. | ||
| − | == Finding the GCD == | + | ==Greatest Common Divisor Video== |
| + | https://youtu.be/HboSeb_gQH8 | ||
| + | |||
| + | == Finding the GCD/GCF of two numbers == | ||
=== Using prime factorization === | === Using prime factorization === | ||
Once the [[prime factorization]]s of the given numbers have been found, the greatest common divisor is the product of all common factors of the numbers. | Once the [[prime factorization]]s of the given numbers have been found, the greatest common divisor is the product of all common factors of the numbers. | ||
| Line 11: | Line 15: | ||
Example: | Example: | ||
| − | <math>270=2\cdot3^3\cdot5</math> and <math>144=2^4\cdot3^2</math>. The common factors are 2 and <math>3^2</math>, so <math>GCD( | + | <math>270=2\cdot3^3\cdot5</math> and <math>144=2^4\cdot3^2</math>. The common factors are 2 and <math>3^2</math>, so <math>GCD(270,144)=2\cdot3^2=18</math>. |
=== Euclidean algorithm === | === Euclidean algorithm === | ||
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>. | 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>. | ||
| − | === Using least common multiple === | + | === Using the least common multiple === |
The GCD of two numbers can also be found using the equation <math>GCD(x, y) \cdot LCM(x, y) = x \cdot y</math>, where <math>LCM(x,y)</math> is the [[least common multiple]] of <math>x</math> and <math>y</math>. | The GCD of two numbers can also be found using the equation <math>GCD(x, y) \cdot LCM(x, y) = x \cdot y</math>, where <math>LCM(x,y)</math> is the [[least common multiple]] of <math>x</math> and <math>y</math>. | ||
| − | ===binary method=== | + | ===The binary method=== |
http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method | http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method | ||
[[Category:Definition]] | [[Category:Definition]] | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
Latest revision as of 21:40, 26 January 2021
This video comprehensively explains everything related to the GCD: https://youtu.be/HboSeb_gQH8 The greatest common divisor (GCD, or GCF (greatest common factor)) 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.
Contents
Greatest Common Divisor Video
Finding the GCD/GCF of two numbers
Using prime factorization
Once the prime factorizations of the given numbers have been found, the greatest common divisor is the product of all common factors of the numbers.
Example:
and 
. The common factors are 2 and 
, so 
.
Euclidean algorithm
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 
.
Using the least common multiple
The GCD of two numbers can also be found using the equation 
, where 
is the least common multiple of 
and 
.
The binary method
http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method
