Difference between revisions of "Greatest common divisor"

Revision as of 21:05, 15 April 2020

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.

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:

$270=2\cdot3^3\cdot5$ and $144=2^4\cdot3^2$ . The common factors are 2 and $3^2$ , so $GCD(270,144)=2\cdot3^2=18$ .

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 $GCD(a_1,\dots,a_n)=GCD(GCD(a_1,\dots,a_{n-1}),a_n)$ .

Using the least common multiple

The GCD of two numbers can also be found using the equation $GCD(x, y) \cdot LCM(x, y) = x \cdot y$ , where $LCM(x,y)$ is the least common multiple of $x$ and $y$ .

The binary method

http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method

@@ Line 1: / Line 1: @@
-The '''greatest common divisor''' ('''GCD''') of two [[integers]] a and b is the largest integer that is a [[divisor]] of both a and b.
+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 GCD of two integers is sometimes called the '''greatest common factor''' ('''GCF''').
+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 several ways.  The first way invlolves factoring both numbers, and the second way uses Euler's Thoerem.
+== Finding the GCD/GCF of two numbers ==
+=== 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 of two numbers has been found, the greatest common divisor is the product of all common factors of the numbers.
 Example:
-<math>270=2\times3^3\times5</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>
-Another 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(270,144)=2\cdot3^2=18</math>.
-<math>1200=2^4\times3\times5</math>
-<math>720=2^4\times3^2\times5</math>
-<math>288=2^5\times3^2</math>
-The common factors are <math>2^4</math> and 3, making the GCD <math>{2^4\times3=48}</math>.
+=== 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>.
-----
+=== 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>.
-Euler's Theorem is much faster and can be used to give the GCD of any two numbers.  Euler's Theorem is primarily faster because you do not need to find the prime factorizations, which can be very time consuming.  Where finding the prime factorization of large numbers fails due to how large the numbers become, Euler's Theorem can be used.
-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:
+===The binary method===
-(1200, 720, 288)
+http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method
-(1200, 720, 576)
+[[Category:Definition]]
-(624, 144, 576)
+[[Category:Number theory]]
-(624, 576, 576)
-(624, 576)
-(48, 576)
-(48, 48), so the GCD is 48.

Page

Toolbox

Search