Greatest Common Divisor

1. Enter two or more "values".
2. The "greatest common denominator" and "common denominator" will be displayed automatically.

The Greatest Common Divisor (GCD) is the largest positive integer that can divide all integers. It is a concept that is frequently used in mathematics and computer science.

Characteristics

• Denominator reductionUsed to simplify fractions.
• Properties of integersLooking up the common factors of numbers helps us understand the properties of integers.

Example

In the case of the numbers 48 and 64

• Divisors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
• Divisors of 64: 1, 2, 4, 8, 16, 32, 64
• Common divisors of both: 1, 2, 4, 8, 16
• Greatest common divisor: 16

Applications

• CryptographyUsed in RSA encryption, etc.
• Integer reductionUsed to simplify fractions and numbers.
• ProgrammingUsed in optimizing numerical calculations and designing algorithms.

How to find the greatest common factor

Method 1. List the factors and find

Find the greatest common factor by following the steps below.

1. List all the factors of each number.
2. Find the common factors.
3. The largest number among them is the greatest common factor.

Example:

• 24 factors: 1, 2, 3, 4, 6, 8, 12, 24
• 36 factors: 1, 2, 3, 4, 6, 9, 12, 18, 36
• Common factors: 1, 2, 3, 4, 6, 12
• Greatest common factor: 12

Method 2. Euclidean algorithm

Euclidean algorithm is an algorithm to find the greatest common factor efficiently.

The calculation is performed as follows.

1. Divide the larger of the two numbers by the smaller number and find the remainder.
2. Repeat this process with the smaller number as the next dividend and the remainder as the next divisor.
3. The divisor when the remainder becomes 0 is the greatest common factor.

Example:

• 24 ÷ 36 = quotient 0, remainder 24
• 36 ÷ 24 = quotient 1, remainder 12
• 24 ÷ 12 = quotient 2, remainder 0
• Since the remainder is 0, the greatest common factor is 12