✦ScienexySCIENCE KNOWLEDGE LIBRARY
topic · SCI-MAT-002-047

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.

NameExpressionDescription

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

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.

Variables

SymbolMeaning

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

NameDescription

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

NameDescription

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

NameDescription

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

NameExpressionDescription

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

ProblemSolutionExplanation

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