Greatest Common Divisors

students, imagine you and a friend are splitting snacks into equal groups 🍎🍪. You want the biggest possible group size that works for both amounts with no leftovers. That idea is at the heart of the greatest common divisor, often written as $\gcd$. In this lesson, you will learn what a greatest common divisor is, how to find it, and why it matters in number theory and proofs.

What is a Greatest Common Divisor?

For two integers $a$ and $b$, a common divisor is any positive integer $d$ such that $d\mid a$ and $d\mid b$. The greatest common divisor of $a$ and $b$ is the largest positive integer that divides both numbers. It is written as $\gcd(a,b)$.

For example, consider $12$ and $18$. The divisors of $12$ are $1,2,3,4,6,12$, and the divisors of $18$ are $1,2,3,6,9,18$. The common divisors are $1,2,3,6, so the greatest common divisor is $\gcd(12,18)=6$.

A key point is that $\gcd(a,b)$ is always positive. Even if one or both numbers are negative, the gcd is defined using positive divisors. For instance, $\gcd(-12,18)=6$.

If $\gcd(a,b)=1$, then $a$ and $b$ are called coprime or relatively prime. This means they share no common positive divisor other than $1$. For example, $8$ and $15$ are coprime because their gcd is $1$.

Why the Greatest Common Divisor Matters

The gcd helps describe how numbers fit together. It tells us the largest chunk size that divides two numbers evenly. This shows up in many real situations 🎯.

Suppose a teacher has $24$ pencils and $36$ erasers and wants to make identical classroom kits with no leftovers. The number of kits must divide both $24$ and $36$. The greatest number of items per kit that works for both counts is $\gcd(24,36)=12$. That means the supplies can be organized into groups of size $12$ in the sense that both numbers are multiples of $12$.

In mathematics, the gcd is also important because it connects to linear combinations, the Euclidean algorithm, and proofs about divisibility. It is one of the main building blocks of number theory.

Finding the GCD by Listing Divisors

The most direct way to find $\gcd(a,b)$ is to list the divisors of each number and look for the largest one they share.

Example: Find $\gcd(20,30)$.

Divisors of $20$: $1,2,4,5,10,20
Divisors of $30$: $1,2,3,5,6,10,15,30
Common divisors: $1,2,5,10

So $\gcd(20,30)=10$.

This method is easy for small numbers, but it becomes slow when numbers get large. Number theory needs a faster method, and that is where the Euclidean algorithm comes in.

The Euclidean Algorithm

The Euclidean algorithm is a fast procedure for finding the gcd of two integers using division. It relies on this fact:

If $a=bq+r$, then any common divisor of $a$ and $b$ also divides $r$.

So the gcd does not change when you replace $a$ by the remainder $r$. In symbols, if $a=bq+r$, then

$$\gcd(a,b)=\gcd(b,r).$$

This is one of the most important facts in elementary number theory.

Example: Find $\gcd(252,105)$.

First divide:

$$252=105\cdot 2+42$$

$$\gcd(252,105)=\gcd(105,42).$$

Next divide:

$$105=42\cdot 2+21$$

$$\gcd(105,42)=\gcd(42,21).$$

Next divide:

$$42=21\cdot 2+0$$

When the remainder becomes $0$, the gcd is the last nonzero remainder. Therefore,

$$\gcd(252,105)=21.$$

This method works efficiently even for large numbers because each step makes the numbers smaller.

GCD and Linear Combinations

A very important idea in number theory is that the gcd of two integers can be written as a linear combination of those integers.

A linear combination of $a$ and $b$ has the form

$$ax+by$$

where $x$ and $y$ are integers.

For example, with $a=12$ and $b=18$, one linear combination is

$$12(2)+18(-1)=24-18=6.$$

Since $6=\gcd(12,18)$, this shows that the gcd can sometimes be expressed as a linear combination.

In fact, the Bézout identity says that for integers $a$ and $b$, there exist integers $x$ and $y$ such that

$$\gcd(a,b)=ax+by.$$

This is a major theorem in number theory. It helps prove many results about divisibility.

Example: Show that $\gcd(21,14)$ can be written as a linear combination.

We know $\gcd(21,14)=7$. Then

$$7=21-14$$

$$7=21(1)+14(-1).$$

That is a linear combination of $21$ and $14$.

A Proof Idea: Why the Euclidean Algorithm Works

students, let’s look at the reasoning behind the Euclidean algorithm. Suppose

$$a=bq+r$$

with $0\le r<b$.

If a number $d$ divides both $a$ and $b$, then $d$ divides $a-bq$. But

$$a-bq=r,$$

so $d\mid r$.

That means every common divisor of $a$ and $b$ is also a common divisor of $b$ and $r$.

The reverse is also true: if $d$ divides both $b$ and $r$, then $d$ divides

$$bq+r=a.$$

So the common divisors of $(a,b)$ and $(b,r)$ are exactly the same. Since they have the same common divisors, they must have the same greatest common divisor:

$$\gcd(a,b)=\gcd(b,r).$$

This is a strong example of basic proof in number theory: we use divisibility properties to prove an algorithm works.

GCD in Divisibility and Basic Proofs

The gcd connects directly to the broader topic of divisibility because it uses the notation $d\mid a$ and $d\mid b$ and depends on the idea of shared factors.

A common proof pattern is:

Assume $d\mid a$ and $d\mid b$.
Use the definition of divisibility to write $a=dm$ and $b=dn$ for some integers $m$ and $n$.
Show that $d$ must also divide another expression made from $a$ and $b$.

For example, if $d\mid a$ and $d\mid b$, then $d$ divides $ax+by$ for any integers $x$ and $y$. Why? Because if $a=dm$ and $b=dn$, then

$$ax+by=(dm)x+(dn)y=d(mx+ny),$$

and $mx+ny$ is an integer. Therefore,

$$d\mid (ax+by).$$

This is useful because it shows every common divisor of $a$ and $b$ must divide every linear combination of them.

That idea helps explain why the gcd is the smallest positive integer that can be expressed as a linear combination of $a$ and $b$, and why the gcd can be used to solve divisibility problems.

Example: Using GCD to Decide Divisibility

Suppose you want to know whether $15$ and $28$ have a common divisor bigger than $1$.

Compute

$$\gcd(15,28).$$

Since $28=15\cdot 1+13$, we get

$$\gcd(15,28)=\gcd(15,13).$$

Then

$$15=13\cdot 1+2,$$

$$\gcd(15,28)=\gcd(13,2).$$

Next,

$$13=2\cdot 6+1,$$

so the gcd is $1$.

Thus $15$ and $28$ are coprime. This tells us they share no factor larger than $1$, which is useful in simplifying fractions and solving congruence problems later in number theory.

Conclusion

Greatest common divisors are a core idea in number theory, students. They describe the largest positive integer dividing two numbers, help identify coprime numbers, and connect strongly to divisibility and linear combinations. You can find a gcd by listing divisors for small numbers, but the Euclidean algorithm is the efficient method for larger numbers. The deeper proof idea is that division with remainder preserves the set of common divisors, which is why the algorithm works. Understanding $\gcd$ gives you a strong foundation for future topics in number theory 🔢.

Study Notes

The greatest common divisor of $a$ and $b$ is written as $\gcd(a,b)$.
$\gcd(a,b)$ is the largest positive integer that divides both $a$ and $b$.
If $\gcd(a,b)=1$, then $a$ and $b$ are coprime.
Common divisors can be found by listing divisors, but that method is best for small numbers.
The Euclidean algorithm uses the rule that if $a=bq+r$, then $\gcd(a,b)=\gcd(b,r)$.
The last nonzero remainder in the Euclidean algorithm is the gcd.
A linear combination has the form $ax+by$, where $x$ and $y$ are integers.
Bézout identity says there exist integers $x$ and $y$ such that $\gcd(a,b)=ax+by$.
If $d\mid a$ and $d\mid b$, then $d\mid(ax+by)$ for any integers $x$ and $y$.
GCD reasoning is a major tool for proofs about divisibility, factorization, and coprime integers.