Greatest common divisor facts for kids

The greatest common divisor (GCD) or highest common factor (HCF) of two integers, let's call them x and y, is the biggest number that can divide both x and y without leaving a remainder. People often write it as GCD(x, y). GCDs are super helpful when you need to make fractions as simple as possible. The ancient Greek mathematician Euclid was the first to come up with this important idea.

How to Find the GCD

Finding the greatest common divisor might sound tricky, but there's a clever method for it! This method is called the Euclidean algorithm. It uses a series of simple division steps to find the GCD of two numbers.

Imagine you want to find the GCD of two numbers. The Euclidean algorithm works by repeatedly dividing the larger number by the smaller number. Then, you replace the larger number with the smaller number, and the smaller number with the remainder you just got. You keep doing this until the remainder is zero. The last non-zero remainder you found is the GCD!

For example, to find the GCD of 20 and 12:

• Divide 20 by 12. You get 1 with a remainder of 8. (20 = 1 × 12 + 8)
• Now, divide 12 by 8. You get 1 with a remainder of 4. (12 = 1 × 8 + 4)
• Next, divide 8 by 4. You get 2 with a remainder of 0. (8 = 2 × 4 + 0)

Since the remainder is now 0, the last non-zero remainder we found was 4. So, the GCD of 20 and 12 is 4.

Examples of GCD

Let's look at a few examples to make it clearer:

The GCD of 20 and 12 is 4. This is because 4 times 5 equals 20, and 4 times 3 equals 12. The numbers 3 and 5 don't share any common factors other than 1, so 4 is the largest number that divides both 20 and 12.

As another example, the GCD of 81 and 21 is 3.

• 81 divided by 3 is 27.
• 21 divided by 3 is 7.
• Since 27 and 7 don't have any common factors (other than 1), 3 is the greatest common divisor.

Related pages

• Coprime
• Euclid's Elements
• Least common multiple

Images for kids

• 

  \gcd(1,x) = y, or Thomae's function. Hatching at bottom indicates ellipses (i.e. omission of dots due to the extremely high density).

See also

In Spanish: Máximo común divisor para niños