Course contentsShow
← Mathematics
Lesson 2711 of 3,12154. Number TheoryFree lesson

Greatest Common Divisor (GCD): Definition

Define the greatest common divisor of two integers and understand its fundamental properties.

Greatest Common Divisor (GCD): Definition

What you'll learn: You'll understand what the greatest common divisor of two integers is and discover its key properties.

The Core Idea

Imagine you have two whole numbers—say 12 and 18. Both are divisible by several numbers: 12 is divisible by 1, 2, 3, 4, 6, and 12, while 18 is divisible by 1, 2, 3, 6, 9, and 18. The numbers that divide both are called common divisors: 1, 2, 3, and 6. The largest of these is 6.

The greatest common divisor (abbreviated GCD) of two integers a and b, denoted gcd(a, b), is the largest positive integer that divides both a and b without leaving a remainder.

Formal Definition

For integers a and b (not both zero), gcd(a, b) is the unique positive integer d such that:

  1. d divides a (written d | a)
  2. d divides b (written d | b)
  3. If c divides both a and b, then c ≤ d

In other words, the GCD is the greatest among all common divisors.

Fundamental Properties

  • Always positive: By definition, gcd(a, b) > 0
  • Sign doesn't matter: gcd(a, b) = gcd(|a|, |b|)
  • Identity with 0: gcd(a, 0) = |a| for any nonzero a
  • Symmetry: gcd(a, b) = gcd(b, a)
  • When gcd = 1: If gcd(a, b) = 1, we say a and b are relatively prime or coprime

Think of It This Way

The GCD is like finding the "largest common measuring stick" that evenly measures two quantities. If you have ropes of length 12 and 18 inches, the longest stick that marks both evenly is 6 inches long.

Key Takeaway: The greatest common divisor of two integers is the largest positive integer that divides both numbers evenly—a fundamental building block for understanding divisibility and number relationships.