English
Greatest common factor by shared primes or the Euclidean algorithm.
Last updated
The Coddy math course teaches the method itself - you work each step on an interactive board and get told exactly where a move went wrong.
A factor of a number divides into it exactly, leaving no remainder: the factors of 12 are 1, 2, 3, 4, 6 and 12. A common factor of two numbers appears in both lists. The greatest common factor is the largest one they share - the biggest number that divides both cleanly.
The GCF of 24 and 36 is 12. Both are divisible by 1, 2, 3, 4, 6 and 12, and 12 is the largest of those. You will also see it called the greatest common divisor (GCD) or the highest common factor (HCF); the three names mean exactly the same thing and which one you were taught is mostly a matter of geography.
Its main job is simplifying. To reduce 24/36 to lowest terms you divide both parts by their GCF: 24 ÷ 12 = 2 and 36 ÷ 12 = 3, giving 2/3 in one step. Dividing by a smaller common factor also works but leaves you going round again - which is the whole reason it is worth finding the greatest one.
Type two or more whole numbers separated by commas or spaces - 24, 36 or 54 24 36. Up to ten at once.
The GCF is at the top. Below it, the same answer is reached by shared prime factors and - for exactly two numbers - by the Euclidean algorithm.
Each row is a prime. The GCF takes the lowest exponent in the row, and any row with a dash in it drops out entirely, because a factor shared by only some of the numbers is not common.
Each line divides and records the remainder, then the next line repeats with the divisor and that remainder. When the remainder hits zero, the previous one is your answer.
The pairs that come up most often, with the reason rather than just the result.
| Numbers | GCF | Why |
|---|---|---|
| 24 and 36 | 12 | Both share 2² and 3 |
| 48 and 18 | 6 | Both share 2 and 3 |
| 8 and 12 | 4 | Both share 2², but only 12 has a 3 |
| 15 and 25 | 5 | Both share a single 5 |
| 8 and 9 | 1 | No shared prime - coprime |
| 7 and 21 | 7 | 7 divides 21, so the smaller number is the GCF |
| 54, 24 and 36 | 6 | 2 and 3 appear in all three |
24, 3624 = 2³ · 3 and 36 = 2² · 3². For each prime take the lower exponent: 2² (since 24 has three 2s but 36 only two) and 3¹ (since 36 has two 3s but 24 only one). That gives 2² · 3 = 12. The Euclidean route agrees: 36 = 1 × 24 + 12, then 24 = 2 × 12 + 0, so the last non-zero remainder is 12.
24, 36The GCF is 12, so divide both parts by it: 24 ÷ 12 = 2 and 36 ÷ 12 = 3, giving 2/3. If you had spotted only the factor 2 you would have got 12/18, then 6/9, then 2/3 - the same place, three steps later. Finding the greatest common factor is what makes it one step.
8, 98 = 2³ and 9 = 3². They have no prime in common, so there is nothing to put in the GCF and the answer is 1. Numbers like this are called coprime. It also means the fraction 8/9 is already in lowest terms and cannot be reduced.
48, 1848 = 2 × 18 + 12. Now repeat with 18 and 12: 18 = 1 × 12 + 6. Repeat with 12 and 6: 12 = 2 × 6 + 0. The remainder is zero, so the previous remainder, 6, is the GCF. Notice that nothing was ever factorised - this is why the method works on numbers hundreds of digits long.
