Number Theory
EN فارسی
Introductory course · Middle school

GCD, LCM and the Euclidean Algorithm

Learning objectives

Common divisors and multiples

Definition

The greatest common divisor \(\gcd(a,b)\) of integers \(a,b\) (not both 0) is the largest positive integer dividing both. Two integers are coprime if \(\gcd(a,b)=1\).

Definition

The least common multiple \(\operatorname{lcm}(a,b)\) of nonzero integers is the smallest positive integer divisible by both.

Example

Divisors of 12: \(1,2,3,4,6,12\). Divisors of 18: \(1,2,3,6,9,18\). The common ones are \(1,2,3,6\), so \(\gcd(12,18)=6\).

Multiples of 4: 4, 8, 12, … and of 6: 6, 12, …, so \(\operatorname{lcm}(4,6)=12\).

Using prime factorizations

Write both numbers as products of primes. The gcd takes the smaller exponent of each prime, and the lcm takes the larger.

Worked example

Find \(\gcd(360,84)\) and \(\operatorname{lcm}(360,84)\).

\[360=2^3\cdot 3^2\cdot 5,\qquad 84=2^2\cdot 3\cdot 7\]

\[\gcd=2^2\cdot 3=12,\qquad \operatorname{lcm}=2^3\cdot 3^2\cdot 5\cdot 7=2520\]

Theorem · gcd times lcm

For positive integers \(a,b\): \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab\).

Show proof

For each prime, if \(a\) and \(b\) contain it with exponents \(x\) and \(y\), then the gcd uses \(\min(x,y)\) and the lcm uses \(\max(x,y)\). Since \(\min(x,y)+\max(x,y)=x+y\), the product of the gcd and the lcm has the same exponent of every prime as \(ab\). ∎

Remark · Check

\(12\cdot 2520=30240=360\cdot 84\)

The Euclidean algorithm

Definition · Division with remainder

For integers \(a\) and \(b>0\) there are unique integers \(q\) and \(r\) with \(a=qb+r\) and \(0\le r<b\).

Theorem · The key fact

If \(a=qb+r\), then \(\gcd(a,b)=\gcd(b,r)\).

Show proof

A common divisor of \(a\) and \(b\) divides \(r=a-qb\), so it is a common divisor of \(b\) and \(r\). Conversely, a common divisor of \(b\) and \(r\) divides \(a=qb+r\). The two pairs have the same common divisors, hence the same greatest one. ∎

Repeat the division, replacing \((a,b)\) by \((b,r)\), until the remainder is 0. The last nonzero remainder is the gcd. Try it with the sliders:

Worked example

Find \(\gcd(252,105)\).

\[252=2\cdot 105+42,\qquad 105=2\cdot 42+21,\qquad 42=2\cdot 21+0\]

The last nonzero remainder is 21, so \(\gcd(252,105)=21\).

Remark · Why it is fast

The remainders shrink quickly: even for numbers with 100 digits the algorithm needs only a few hundred steps. It appears in the Elements of Euclid, written around 300 BCE.

Simplifying fractions

Worked example

Put \(\frac{252}{105}\) in lowest terms.

Since \(\gcd(252,105)=21\), divide both numbers by 21: \(\frac{252}{105}=\frac{12}{5}\).

Remark

A fraction \(\frac ab\) is in lowest terms exactly when \(\gcd(a,b)=1\). This is the idea behind lowest terms in the lesson on rational numbers.

Exercises

Find \(\gcd(84,126)\) and \(\operatorname{lcm}(84,126)\) using prime factorizations.

Show solution

\(84=2^2\cdot 3\cdot 7\) and \(126=2\cdot 3^2\cdot 7\). So \(\gcd=2\cdot 3\cdot 7=42\) and \(\operatorname{lcm}=2^2\cdot 3^2\cdot 7=252\).

Use the Euclidean algorithm to find \(\gcd(1071,462)\).

Show solution

\(1071=2\cdot 462+147\), \(462=3\cdot 147+21\), \(147=7\cdot 21+0\). So \(\gcd(1071,462)=21\).

Two bells ring every 12 and every 18 minutes. They ring together at noon. When do they next ring together?

Show solution

The next common time is the lcm: \(\operatorname{lcm}(12,18)=36\), so after 36 minutes.

Prove that consecutive integers \(n\) and \(n+1\) are coprime.

Show solution

A common divisor of \(n\) and \(n+1\) divides their difference \((n+1)-n=1\), so the gcd is 1.

Put \(\frac{168}{294}\) in lowest terms.

Show solution

\(294=1\cdot 168+126\), \(168=1\cdot 126+42\), \(126=3\cdot 42+0\), so \(\gcd=42\) and \(\frac{168}{294}=\frac{4}{7}\).

Find two positive integers with gcd 6 and lcm 36.

Show solution

Their product is \(6\cdot 36=216\). Try 12 and 18: \(\gcd(12,18)=6\), \(\operatorname{lcm}(12,18)=36\) and \(12\cdot 18=216\). (The pair 6 and 36 also works.)

Summary