The GCD of two or more positive integers is the largest positive integer that divides every given number without leaving a remainder. For example, the factors of 24 include 1, 2, 3, 4, 6, 8, 12 and 24, while the factors of 36 include 1, 2, 3, 4, 6, 9, 12, 18 and 36. Their greatest common factor is 12. The GCD can be calculated using factor listing, prime factorization or the Euclidean algorithm. When prime factorization is used, the common prime factors are selected with the smallest exponents. The GCD is particularly useful when dividing quantities into the largest possible equal groups.
Greatest Common Divisor (GCD/HCF)
The Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF), is the largest positive integer that divides two or more integers exactly. It is useful for simplifying fractions and solving problems involving equal grouping.
| Name | Expression | Description |
|---|---|---|
GCD Definition | GCD(a, b) = greatest positive common divisor of a and b | The GCD is the largest positive integer that divides both numbers. |
Prime Factorization Method | GCD(a,b) = product of common prime factors raised to their minimum exponents | For each prime appearing in both factorizations, use the smaller exponent. |
Euclidean Algorithm | GCD(a,b) = GCD(b, a mod b), for b ≠ 0 | The GCD remains unchanged when the larger number is replaced by its remainder after division by the smaller number. |
Multiple-Integer GCD | GCD(a,b,c) = GCD(GCD(a,b),c) | The GCD of several integers can be found by calculating the GCD successively. |
Explanation
Variables
| Symbol | Meaning |
|---|---|
a | The first positive integer. |
b | The second positive integer. |
c | An additional positive integer. |
r | The remainder in the Euclidean algorithm. |
p | A common prime factor. |
e | The smaller exponent of a common prime factor. |
Example or application
A worked example has not yet been added.
Definition
The Greatest Common Divisor of two or more integers, also known as the Highest Common Factor, is the largest positive integer that divides all the given integers exactly.
Purpose
The GCD is used to identify the largest shared divisor, simplify fractions, divide quantities into equal groups and solve number theory problems.
Importance
It is fundamental to arithmetic, fraction simplification, divisibility, the Euclidean algorithm, algebra and applications involving equal distribution.
Key Concepts
| Name | Description |
|---|---|
Greatest Common Divisor | The largest positive integer that divides all given integers exactly. |
Highest Common Factor | Another name for the greatest common divisor. |
Common Divisor | A positive integer that divides every given number. |
Prime Factorization Method | A method of finding GCD by selecting common prime factors with their smallest exponents. |
Euclidean Algorithm | An efficient repeated-division method for finding the GCD. |
Characteristics
The GCD is always a positive integer for positive input integers.
The GCD divides every given integer exactly.
No common divisor is greater than the GCD.
The GCD of two equal positive integers is the integer itself.
The GCD of two coprime positive integers is 1.
The GCD can be calculated using factor lists, prime factorization or the Euclidean algorithm.
The GCD is never greater than the smallest positive input integer.
Types
| Name | Description |
|---|---|
GCD of Two Integers | The greatest positive divisor shared by two positive integers. |
GCD of Multiple Integers | The greatest positive integer that divides every number in a given set. |
Coprime Pair | Two positive integers whose GCD is 1. |
GCD Using Prime Factorization | A method based on selecting shared prime factors with minimum exponents. |
GCD Using Euclidean Algorithm | A method based on repeated division and remainders. |
Components
| Name | Description |
|---|---|
Input Integers | The positive integers for which the GCD is being calculated. |
Common Divisors | The positive integers that divide every input number. |
Greatest Divisor | The largest element among the common divisors. |
Prime Factors | The shared prime factors used in the prime factorization method. |
Properties
| Name | Expression | Description |
|---|---|---|
Commutative Property | GCD(a,b) = GCD(b,a) | Changing the order of the two integers does not change the GCD. |
Identity with Zero | GCD(a,0) = |a| | For a nonzero integer a, its GCD with zero is its absolute value. |
Coprime Numbers | GCD(a,b) = 1 | Two integers are coprime when their only positive common factor is 1. |
GCD with Equal Numbers | GCD(a,a) = a | The GCD of a positive integer with itself is that integer. |
Scaling Property | GCD(ka,kb) = k × GCD(a,b), for k > 0 | Multiplying both positive integers by the same positive integer multiplies their GCD by that integer. |
Examples
| Problem | Solution | Explanation |
|---|---|---|
Find the GCD of 24 and 36 using factors. | Common factors are 1, 2, 3, 4, 6 and 12. Therefore, GCD = 12. | The largest number that divides both 24 and 36 exactly is 12. |
Find the GCD of 60 and 90 using prime factorization. | 60 = 2^2 × 3 × 5 and 90 = 2 × 3^2 × 5. GCD = 2 × 3 × 5 = 30. | Select the common prime factors 2, 3 and 5 using their smallest exponents. |
Find the GCD of 48 and 18 using the Euclidean algorithm. | 48 = 18 × 2 + 12; 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. Therefore, GCD = 6. | The last nonzero remainder is the greatest common divisor. |
Find the greatest number of equal groups that can be formed from 36 apples and 48 oranges without leftovers, with each group having the same number of apples and oranges. | GCD(36,48) = 12. Therefore, 12 equal groups can be formed. | The greatest common divisor gives the maximum number of identical groups into which both quantities can be divided exactly. |
Applications
Simplifying fractions to lowest terms.
Dividing objects into the largest possible equal groups.
Finding common factors of integers.
Solving mathematical problems involving equal distribution.
Reducing ratios to simplest form.
Calculating LCM using the GCD relationship.
Prerequisites
Understanding of factors and multiples.
Knowledge of prime and composite numbers.
Understanding of prime factorization.
Basic division and remainders.
Familiarity with common factors.
Learning Objectives
Define GCD and HCF.
Identify the common factors of two or more integers.
Calculate GCD using factor listing.
Calculate GCD using prime factorization.
Apply the Euclidean algorithm.
Recognize coprime integers.
Apply GCD to equal-grouping and fraction-simplification problems.
Common Mistakes
Choosing the smallest common factor instead of the greatest one.
Selecting all prime factors instead of only common prime factors.
Using the larger exponent in the prime factorization method.
Stopping the Euclidean algorithm before the remainder becomes zero.
Confusing GCD with LCM.
Assuming that two different integers cannot have a GCD of 1.
Practice Questions
Find the GCD of 18 and 30.
Calculate the GCD of 72 and 96 using prime factorization.
Find the GCD of 105 and 252 using the Euclidean algorithm.
Determine whether 35 and 64 are coprime.
Find the GCD of 24, 36 and 60.
A teacher has 48 pencils and 60 pens. Find the maximum number of identical groups that can be made without leftovers.
Key Takeaway
The GCD or HCF is the largest positive integer that divides all given integers exactly. It can be found through factor listing, prime factorization or the Euclidean algorithm.
Related Topics
SCI-MAT-002-044
SCI-MAT-002-045
SCI-MAT-002-046
SCI-MAT-002-048
SCI-MAT-002-049
SCI-MAT-002-050
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory