Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Greatest common divisor"

m (Changed * to \cdot)
 
(13 intermediate revisions by 7 users not shown)
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.
+
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 GCD is sometimes called the '''greatest common factor''' ('''GCF''').
 
The GCD is sometimes called the '''greatest common factor''' ('''GCF''').
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.
  
 +
==Greatest Common Divisor Video==
 +
https://youtu.be/HboSeb_gQH8
  
 +
== 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.
  
−
The GCD can be found in two ways.  The first way involves factoring the numbers, and the second way uses [[Euclidean algorithm]].
+
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>.
  
−
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.
+
=== 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>.
  
−
Example:<br>
+
=== Using the least common multiple ===
−
<math>270=2\times3^3\times5</math><br>
+
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>.
−
<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 binary method===
−
 
+
http://en.wikipedia.org/wiki/Greatest_common_divisor#Binary_method
−
Another Example:<br>
+
[[Category:Definition]]
−
<math>1200=2^4\times3\times5</math><br>
+
[[Category:Number theory]]
−
<math>720=2^4\times3^2\times5</math><br>
 
−
<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>.
 
−
 
 
−
----
 
−
 
 
−
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>\displaystyle GCD(a_1,\dots,a_n)=GCD(GCD(a_1,\dots,a_{n-1}),a_n)</math>.
 
−
 
 
−
----
 
−
 
 
−
Another useful trick is the equation
 
−
 
 
−
<math>GCD(x, y) \cdot LCM(x, y) = x \cdot y</math>
 
−
 
 
−
Using this, you can find the GCD rather quickly if you know the LCM and the two numbers.  This equation is also useful for finding one of the numbers if you know the other number, the GCD and the LCM.
 

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.

Greatest Common Divisor Video

https://youtu.be/HboSeb_gQH8

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Greatest_common_divisor&oldid=143377"