- Calculators
- ::
- Numbers
- ::
- GCD Calculator
GCD calculator
The greatest common division calculator computes GCD of two or more integers. Calculator implements four different computation methods: prime factorization, repeated division, Euclidean algorithm and listing out the factors.
Find Greatest Common Divisor of 512 and 768, using prime factorization.
solution
The GCD of given numbers is 256.
explanation
Step 1 : Find prime factorization of each number.
$$\begin{aligned}512 =& 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\\[8pt]768 =& 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot3\\[8pt]\end{aligned}$$(view steps on how to factor 512 and 768. )
Step 2 : Put a box around factors that are common for all numbers:
$$\begin{aligned}512 =& \color{blue}{\boxed{2}}\cdot\color{red}{\boxed{2}}\cdot\color{Fuchsia}{\boxed{2}}\cdot\color{Orange}{\boxed{2}}\cdot\color{Purple}{\boxed{2}}\cdot\color{blue}{\boxed{2}}\cdot\color{red}{\boxed{2}}\cdot\color{Fuchsia}{\boxed{2}}\cdot2\\[8pt]768 =& \color{blue}{\boxed{2}}\cdot\color{red}{\boxed{2}}\cdot\color{Fuchsia}{\boxed{2}}\cdot\color{Orange}{\boxed{2}}\cdot\color{Purple}{\boxed{2}}\cdot\color{blue}{\boxed{2}}\cdot\color{red}{\boxed{2}}\cdot\color{Fuchsia}{\boxed{2}}\cdot3\\[8pt]\end{aligned}$$Step 3 : Multiply the boxed numbers together:
$$ GCD = 2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2 = 256 $$This solution can be visualized using a Venn diagram.
The GCD equals the product of the numbers at the intersection.
The GCD equals the product of the numbers at the intersection.
What is Greatest common factor (GCF)?
The greatest common divisor (multiple) of two integers is the largest number that divides them both. This calculator provides four methods to compute GCD. We'll show them with a few examples.
Method 1 : Find GCD using prime factorization method
Example: find GCD of 36 and 48
Step 1: find prime factorization of each number:
42 = 2 * 3 * 7
70 = 2 * 5 * 7
Step 2: circle out all common factors:
42 = ② * 3 * ⑦
70 = ② * 5 * ⑦
We see that the GCD is ② * ⑦ = 14
Method 2 : Find GCD using a repeated division
Example: find GCD of 84 and 140.
Step 1: Place the numbers inside division bar:
| 84 | 140 |
Step 2: Divide both numbers by 2:
| 2 | 84 | 140 |
| 42 | 70 |
Step 3: Continue to divide until the numbers do not have a common factor.
| ② | 84 | 140 |
| ② | 42 | 70 |
| ⑦ | 21 | 35 |
| 3 | 7 |
Step 4: The GCD of 84 and 140 is: ② * ② * ⑦ = 28
Method 3 : Euclidean algorithm
Example: Find GCD of 52 and 36, using Euclidean algorithm.
Solution: Divide 52 by 36 and get the remainder, then divide 36 with the remainder from previous step. When the remainder is zero the GCD is the last divisor.
| 52 | : | 36 | = | 1 | remainder (16) | ||||
| 36 | : | 16 | = | 1 | remainder (4) | ||||
| 16 | : | ④ | = | 4 | remainder (0) | ||||
We conclude that the GCD = 4.
Method 4 : Listing out the factors
Example: find GCD of 45 and 54 by listing out the factors.
Step 1: Find divisors for the given numbers:
The divisors of 45 are 1, 3, 5, ⑨, 15 and 45
The divisors of 54 are 1, 2, 3, 6, ⑨ 18, 27 and 54
Step 2: The greatest divisor = ⑨
1. GCD Definition, Methods, Examples
2. Euclidean Algorithm - video tutorial
3. Program to Find GCD - code implementation in C++, C, Java, Python, C# and Javascript.