Greatest Common Divisor
The GCD is the largest number that divides two numbers exactly.
About this topic
The greatest common divisor (GCD, also called HCF) is the largest number that divides two or more numbers exactly. For 24 and 36 it is 12. You can find it by listing factors, by comparing prime factorizations, or with Euclid's algorithm, which repeatedly replaces the larger number by the remainder of dividing.
With prime factorizations, 24 = 2³ × 3 and 36 = 2² × 3², so the GCD takes the lowest power of each shared prime: 2² × 3 = 12. With Euclid's algorithm, 36 ÷ 24 leaves remainder 12, then 24 ÷ 12 leaves 0, so the last non-zero remainder, 12, is the answer. This method is fast even for huge numbers and is more than two thousand years old.
The GCD is the tool for simplifying fractions: divide the numerator and denominator by it and the fraction is in lowest terms. For 24/36, dividing both by 12 gives 2/3. It also solves sharing problems, such as cutting two ribbons of 24 cm and 36 cm into the longest equal pieces with nothing left over, which gives 12 cm pieces. Tiling a floor with the biggest square tiles uses the same idea.
A common confusion is mixing up GCD and LCM. The GCD is never larger than the smaller number, while the LCM is never smaller than the larger one. When the GCD of two numbers is 1, they are called coprime or relatively prime, even if neither number is itself prime.
Key ideas
- List or factor to find common divisors
- Euclid's algorithm repeats remainders
- Use the GCD to simplify fractions
Quick check
Use cases: where Greatest Common Divisor helps
- Homework: review the key idea behind Greatest Common Divisor before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Greatest Common Divisor without notes.
- Visual learning: play with the interactive lab to see how Greatest Common Divisor changes when you adjust its inputs.
- Teaching a friend: explain Greatest Common Divisor in your own words, then compare your version with the key ideas.
Number and algebra skills are used in science, engineering, budgeting and computing.
Frequently asked questions
What is Greatest Common Divisor?
The GCD is the largest number that divides two numbers exactly.
What will I learn in Greatest Common Divisor?
List or factor to find common divisors. Euclid's algorithm repeats remainders. Use the GCD to simplify fractions.
Is Greatest Common Divisor part of Mathematics?
Yes. It is one of 200 Mathematics topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Greatest Common Divisor lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Greatest Common Divisor?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.