7.1 Divisibility, gcd, and integer equations

Why integer arithmetic needs new language

Integer arithmetic looks familiar, but proofs about integers need vocabulary that is more precise than ordinary division. When we write $a/b$ in real algebra, the quotient usually exists as a real number. In integer arithmetic, the important question is different: can the quotient be chosen as another integer?

This question controls many later methods. It lets us define prime numbers, measure common factors, compute greatest common divisors efficiently, and decide when an equation such as

$$ax+by=c$$

has integer solutions.

Divisibility

Definition

Divisibility

Let $a,b\in\mathbb Z$. We say that $a$ divides $b$, written $a\mid b$, if there exists an integer $d$ such that

$$b=ad.$$

In that case, $a$ is called a divisor or factor of $b$.

The phrase "there exists an integer" is the essential part of the definition. For example, $3\mid 15$ because $15=3\cdot5$, while $4\nmid 15$ because there is no integer $d$ with $15=4d$.

Several edge cases are worth fixing immediately:

• every integer divides $0$, because $0=a\cdot0$;
• $0$ divides only $0$, because $x=0\cdot d$ forces $x=0$;
• $\pm1$ divides every integer;
• if $a\ne0$, then both $a$ and $-a$ divide $a$.

Theorem

Basic divisibility rules

Let $a,b,c\in\mathbb Z$.

1. If $b\ne0$ and $a\mid b$, then $|a|\le |b|$.
2. If $a\mid b$, then $(\pm a)\mid(\pm b)$.
3. If $a\mid b$ and $b\mid c$, then $a\mid c$.
4. If $a\mid b$ and $a\mid c$, then $a\mid (bx+cy)$ for all $x,y\in\mathbb Z$.

The fourth rule is the one that quietly powers much of the chapter. If a number divides two integers, then it divides every integer linear combination of them. For instance, if $6\mid 18$ and $6\mid 30$, then

$$6\mid 18x+30y$$

for every pair of integers $x,y$.

To prove the combination rule, write $b=am$ and $c=an$ with integer $m,n$. Then $bx+cy=a(mx+ny)$, and the new multiplier is still an integer. This argument uses no division by $a$, so it remains valid when $a=0$.

Primes, composites, and well-ordering

Definition

Prime and composite

Let $n\in\mathbb Z^+$ with $n\gt 1$.

• $n$ is prime if its only positive divisors are $1$ and $n$;
• $n$ is composite if it is not prime.

The integer $1$ is neither prime nor composite.

Equivalently, $n\gt 1$ is composite exactly when

$$n=n_1n_2$$

for integers $n_1,n_2$ satisfying $1\lt n_1,n_2\lt n$.

The proofs about prime numbers rely on a simple but powerful ordering fact.

Theorem

Well-ordering principle

Every nonempty subset of $\mathbb N=\{0,1,2,\ldots\}$ has a least element.

A least element must belong to the set; a lower bound need not. The real interval $(0,1]$ has lower bound $0$ but no least element, since $x/2$ is a smaller member whenever $x$ is a member. To obtain well-ordering from strong induction, suppose a subset of $\mathbb N$ has no least element. It cannot contain $0$. If it contains none of $0,\ldots,n$, it cannot contain $n+1$ either, since that would be least. Induction shows the subset is empty.

This principle is a way to run a least-counterexample argument. If a bad set of positive integers is nonempty, choose its least bad element and show that this least element creates an even smaller bad element. That contradiction proves that the bad set was empty.

Theorem

Every integer greater than 1 has a prime factor

Every positive integer $n\gt 1$ is divisible by at least one prime.

Here is the proof pattern. Suppose the claim fails, and let $m$ be the least integer greater than $1$ with no prime factor. Then $m$ cannot itself be prime. So $m=n_1n_2$ with $1\lt n_1,n_2\lt m$. By minimality of $m$, the smaller number $n_1$ has a prime factor $p$. Since $p\mid n_1$ and $n_1\mid m$, transitivity gives $p\mid m$, contradicting the choice of $m$.

Theorem

Infinitely many primes

There are infinitely many prime numbers.

If there were only finitely many primes $p_1,\ldots,p_N$, consider

$$n=p_1p_2\cdots p_N+1.$$

The previous theorem gives a prime divisor of $n$. That prime must be one of the listed primes, say $p_i$. But $p_i$ also divides the product $p_1p_2\cdots p_N$, so it divides the difference

$$n-p_1p_2\cdots p_N=1,$$

which is impossible for a prime.

Greatest common divisors

Definition

Greatest common divisor

Let $a,b\in\mathbb Z$. If at least one of $a,b$ is nonzero, the greatest common divisor is

$$\gcd(a,b)=\max\{d\in\mathbb Z:d\mid a\text{ and }d\mid b\}.$$

If $a=b=0$, define $\gcd(0,0)=0$.

For nonzero input, the maximum exists because the possible common divisors are bounded in absolute value. Also, $\gcd(a,b)$ is always positive unless both inputs are zero.

Changing either sign preserves divisibility, so $\gcd(a,b)=\gcd(|a|,|b|)$. In particular, $\gcd(a,0)=|a|$. The value $\gcd(0,0)=0$ is a separate convention: all positive integers divide both inputs, so there is no greatest positive common divisor in that case.

Definition

Relatively prime

Two nonzero integers $a$ and $b$ are relatively prime if their only positive common divisor is $1$. Equivalently,

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

For inputs that are not both zero, the gcd removes their common part. If

$$d=\gcd(a,b),$$

then

$$\gcd\left(\frac ad,\frac bd\right)=1.$$

Indeed, a positive common divisor $e$ of $a/d$ and $b/d$ makes $de$ a common divisor of $a,b$. Since $d>0$ is greatest, $de\le d$, so $e\le1$. Thus $e=1$. Dividing by $d$ would be invalid for the excluded pair $(0,0)$.

For example, $\gcd(126,140)=14$, so

$$\frac{126}{140}=\frac{9}{10},$$

and $9$ and $10$ are relatively prime.

The division algorithm

The next task is computational: how do we find the gcd without already knowing all common divisors? The key is integer division with a controlled remainder.

Theorem

Division algorithm

Let $a,b\in\mathbb Z$ with $b\ne0$. Then there exist unique integers $q$ and $r$ such that

$$a=bq+r,\qquad 0\le r\lt|b|.$$

The integer $q$ is the quotient and $r$ is the remainder.

The condition $0\le r\lt|b|$ is not decoration. It is what makes the remainder unique. For example,

$$17=5\cdot3+2$$

has an allowed remainder $2$, while

$$17=5\cdot2+7$$

does not count as the division algorithm because $7$ is not smaller than $5$.

For existence, first take $a\ge0$ and $b>0$. The set

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}$$

contains $a$, so well-ordering supplies a least member $r=a-bq$. If $r\ge b$, then $r-b=a-b(q+1)$ would be a smaller nonnegative member. Hence $0\le r\lt b$. If $a\lt0$ and $b>0$, the integer $A=a+(-a)b=(-a)(b-1)$ is nonnegative. Divide $A=bQ+r$ by the case just proved; rearranging gives $a=b(Q+a)+r$ with the same allowed remainder. For $b\lt0$, divide by $B=|b|>0$ and replace the resulting quotient $Q$ by $-Q$. Thus no sign case requires a negative remainder.

For uniqueness, suppose $a=bq+r=bq'+r'$ with both remainders in range. Then $b(q-q')=r'-r$, but $|r'-r|\lt|b|$. A nonzero integer multiple of $b$ has absolute value at least $|b|$, so $r'=r$. Since $b\ne0$, the remaining equality forces $q'=q$. The strict upper bound proves uniqueness; merely requiring a nonnegative remainder would not.

Common mistake

Do not ignore the remainder range

The equation $a=bq+r$ alone is not enough. There are infinitely many such representations if $r$ is unrestricted, because changing $q$ changes $r$. The inequality $0\le r\lt|b|$ is what selects the canonical quotient and remainder.

Gcd invariance and the Euclidean algorithm

The division algorithm is useful because replacing $(a,b)$ by $(b,r)$ preserves the gcd.

Theorem

Gcd step

If $a=bq+r$, then

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

Proof: Preserve the entire set of common divisors

The target is equality of two gcds. A stronger intermediate statement makes the proof direct: an integer $h$ divides both $a,b$ exactly when it divides both $b,r$. In the forward direction use $r=a-bq$; in the reverse direction use $a=bq+r$. Both steps use closure under integer linear combinations.

The two divisor sets therefore have the same greatest element when the inputs are not both zero. If $a=b=0$, then $r=0$ and both gcds equal $0$ by convention. The identity itself does not need a remainder bound; the bound is needed to make the algorithm progress.

Concept lensAlgorithmic

An invariant and a decreasing computation

The gcd is the quantity preserved by each replacement $(a,b)\mapsto(b,r)$. The remainder is the quantity made smaller. These serve different purposes: preservation proves that the final answer is the original gcd, while strict decrease proves that a final step will occur. Start with absolute values, swap to put the larger positive input first, and stop immediately if the other input is zero. In every remaining division the divisor is positive.

Worked example

Euclidean algorithm for $\gcd(7224,1290)$

Apply the division algorithm repeatedly:

$$\begin{aligned} 7224&=1290\cdot5+774,\\ 1290&=774\cdot1+516,\\ 774&=516\cdot1+258,\\ 516&=258\cdot2+0. \end{aligned}$$

The last nonzero remainder is $258$, so

$$\gcd(7224,1290)=258.$$

The algorithm must terminate because the remainders form a strictly decreasing sequence of nonnegative integers:

$$r_1>r_2>r_3>\cdots\ge0.$$

A strictly decreasing sequence of nonnegative integers cannot continue forever.

Extended Euclidean algorithm and Bézout's identity

The same computation can be run backward to express the gcd as an integer linear combination of the original two numbers.

Worked example

Back-substitution

From the previous computation,

$$258=774-516.$$

Substitute $516=1290-774$:

$$258=774-(1290-774)=2\cdot774-1290.$$

Substitute $774=7224-5\cdot1290$:

$$258=2(7224-5\cdot1290)-1290 =2\cdot7224-11\cdot1290.$$

Thus

$$258=7224\cdot2+1290\cdot(-11).$$

Back-substitution can also be organized forward. For positive inputs put $r_0=a$, $r_1=b$, and keep coefficients $r_k=s_ka+t_kb$, starting with $(s_0,t_0)=(1,0)$ and $(s_1,t_1)=(0,1)$. If $r_{k+2}=r_k-q_{k+1}r_{k+1}$, then

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

Substituting the two known linear combinations proves this update. Every coefficient remains integral, and the row for the last nonzero remainder supplies the required coefficients of the gcd.

From Euclidean division to Bézout coefficients

The downward Euclidean computation and the upward back-substitution are not two separate tricks. They are the same division equations read in opposite directions: first to locate the last nonzero remainder, then to rewrite that remainder using the original two integers.

Follow the Euclidean algorithm first find the gcd and then reverse into a concrete Bézout identity for integer equations.

1. First division

   The computation starts with 7224=1290*5+774, so the next pair is (1290,774).

2. Gcd invariant

   If a=bq+r, then the positive common divisors of (a,b) are exactly the positive common divisors of (b,r).

3. Remainder chain

   The remainders 774, 516, 258, 0 show that the last nonzero remainder is gcd(7224,1290)=258.

4. Back-substitution

   Running the equations backward first gives 258=2*774-1290.

5. Bézout combination

   Substituting 774=7224-5*1290 gives the concrete identity 258=2*7224-11*1290.

6. Equation test

   A linear integer equation ax+by=c has integer solutions exactly when gcd(a,b) divides c.

The Euclidean algorithm moves downward through smaller remainders to find the gcd. The extended algorithm then reads the same equations backward to express that gcd as a Bézout combination, which is why gcd(a,b) controls when ax+by=c has integer solutions.

Theorem

Bézout's identity

For any integers $a,b$, there exist integers $x,y$ such that

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

For signed nonzero inputs, compute using $|a|,|b|$ and absorb their signs into the resulting coefficients. If one input is zero, use $|a|=a\operatorname{sgn}(a)$ or its counterpart for $b$; for $(0,0)$ use $x=y=0$. This proves all cases of the identity.

When the inputs are not both zero, the gcd is also the smallest positive integer linear combination. It is such a combination by the identity, and every positive combination is a positive multiple of the gcd, hence at least as large. For $(0,0)$ there is no positive combination.

Theorem

Relative primality criterion

Let $a,b$ be nonzero integers. Then $a$ and $b$ are relatively prime if and only if there exist integers $x,y$ such that

$$ax+by=1.$$

One direction is Bézout's identity when $\gcd(a,b)=1$. For the converse, if $ax+by=1$, then every common divisor of $a$ and $b$ must divide $1$; hence the greatest positive common divisor is $1$.

Worked example

Extended Euclidean table

For $12345$ and $11111$, the Euclidean algorithm gives

$$\begin{aligned} 12345&=11111\cdot1+1234,\\ 11111&=1234\cdot9+5,\\ 1234&=5\cdot246+4,\\ 5&=4\cdot1+1,\\ 4&=1\cdot4+0. \end{aligned}$$

So the gcd is $1$. Back-substitution, or the coefficient table form of the extended Euclidean algorithm, gives

$$1=12345(-2224)+11111(2471).$$

The successive coefficient pairs are

$$(1,0),\ (0,1),\ (1,-1),\ (-9,10),\ (2215,-2461),\ (-2224,2471).$$

For example, the row for remainder $4$ comes from $(1,-1)-246(-9,10)=(2215,-2461)$. The next row subtracts this pair from $(-9,10)$ and yields the displayed identity.

This proves in particular that $12345$ and $11111$ are relatively prime.

Common divisors and Euclid's lemma

Bézout's identity also gives a cleaner characterization of the gcd.

Theorem

Common divisors divide the gcd

For integers $a,b,n$,

$$n\mid a\text{ and }n\mid b \quad\Longleftrightarrow\quad n\mid \gcd(a,b).$$

The forward direction is the useful one. If $n$ divides both $a$ and $b$, then it divides every linear combination $ax+by$; in particular, it divides the Bézout combination equal to $\gcd(a,b)$.

Theorem

Euclid's lemma

Let $p$ be prime. If $p\mid ab$, then $p\mid a$ or $p\mid b$.

If $p\nmid a$, then $\gcd(a,p)=1$, so there exist integers $m,n$ with

$$am+pn=1.$$

Multiplying by $b$ gives

$$abm+pbn=b.$$

Since $p\mid ab$, both terms on the left are divisible by $p$, so $p\mid b$.

The same proof gives cancellation without assuming primality: if $\gcd(u,v)=1$ and $v\mid ut$, then $v\mid t$. Multiply a Bézout identity $u\alpha+v\beta=1$ by $t$; both terms on the left are divisible by $v$. This applies to signed integers and will justify the parameter step in integer equations below.

For example, if $a\mid c$, $b\mid c$, and $\gcd(a,b)=1$, then $ab\mid c$. Write $c=at$ with integer $t$. Since $b\mid at$, coprime cancellation gives $b\mid t$, so $t=bk$ and $c=abk$ for an integer $k$. The coprimality condition matters: $4\mid12$ and $6\mid12$, but $24\nmid12$.

Unique prime factorization

Theorem

Fundamental theorem of arithmetic

Every positive integer greater than $1$ can be written as a product of primes, and this product is unique up to the order of the factors.

Existence follows from the same least-counterexample strategy used earlier. If there were a least integer greater than $1$ that could not be written as a product of primes, it would not be prime, so it would split into smaller factors, and those smaller factors would already have prime factorizations.

Uniqueness uses Euclid's lemma. If

$$p_1p_2\cdots p_r=q_1q_2\cdots q_s,$$

then $p_1$ divides the right-hand product, so $p_1$ must divide one of the prime factors $q_j$. Hence $p_1=q_j$. Cancel and repeat.

Repeating Euclid's lemma reduces divisibility of a finite product to one factor. Cancellation cannot exhaust only one prime list: that would leave $1$ equal to a nonempty product of primes, which is greater than $1$. Thus the lists have the same length and the same factors with multiplicity.

For positive integers $a,b$, the theorem lets us compare exponents. If

$$a=p_1^{m_1}\cdots p_r^{m_r}, \qquad b=p_1^{n_1}\cdots p_r^{n_r},$$

where missing primes have exponent $0$, then

$$\gcd(a,b)=p_1^{\min(m_1,n_1)}\cdots p_r^{\min(m_r,n_r)}.$$

In the same notation, $a\mid b$ exactly when $m_i\le n_i$ for every prime. A positive common divisor can use at most $\min(m_i,n_i)$ copies of each prime. Taking all these allowed copies gives a common divisor divisible by every other one. For signed nonzero inputs apply this description to absolute values; zero is handled by the gcd convention instead.

Worked example

Gcd from prime powers

Since

$$144=2^4\cdot3^2,\qquad 60=2^2\cdot3\cdot5,$$

we have

$$\gcd(144,60)=2^2\cdot3^1\cdot5^0=12.$$

Linear Diophantine equations

An equation

$$ax+by=c$$

where the unknowns $x,y$ must be integers is called a linear Diophantine equation. Bézout's identity tells us exactly when it is solvable.

Theorem

Solvability criterion

Let $a,b,c\in\mathbb Z$ and let $d=\gcd(a,b)$. The equation

$$ax+by=c$$

has an integer solution $(x,y)$ if and only if $d\mid c$.

If a solution exists, then $d$ divides $a$ and $b$, so $d$ divides $ax+by=c$. Conversely, if $c=dr$, Bézout's identity gives $d=am+bn$, and then

$$c=dr=a(mr)+b(nr).$$

Thus $(mr,nr)$ is a solution.

First suppose $a,b$ are both nonzero. Once one solution is known, all solutions can be described. With $d=\gcd(a,b)>0$, put

$$u=\frac ad,\qquad v=\frac bd,$$

and let $(x_0,y_0)$ be one solution. Then every solution is

$$x=x_0+kv,\qquad y=y_0-ku,\qquad k\in\mathbb Z.$$

There are two claims to prove. Substitution shows that every displayed pair is a solution, since the extra terms cancel: $a(kv)-b(ku)=0$. For completeness, subtract the equation for $(x_0,y_0)$ from any other solution:

$$u(x-x_0)=-v(y-y_0).$$

Since $\gcd(u,v)=1$, the cancellation result gives $v\mid(x-x_0)$. Write $x-x_0=kv$. Substitution and cancellation of the nonzero integer $v$ then give $y-y_0=-ku$. This establishes that there are no other solutions; finding several pairs by trial would not prove completeness.

Handle zero coefficients before this cancellation. If $a=0$, $b\ne0$, solutions exist precisely when $b\mid c$; then $y=c/b$ and $x$ is any integer. If $b=0$, $a\ne0$, then $x=c/a$ and $y$ is arbitrary, provided $a\mid c$. If $a=b=0$, every integer pair solves the equation when $c=0$, and no pair does when $c\ne0$. This agrees with $0\mid c$ exactly when $c=0$, without dividing by the zero gcd.

Worked example

A measuring problem

Can a $180$ mL cup and a $105$ mL glass measure exactly $30$ mL? Algebraically, we ask whether

$$180x+105y=30$$

has integer solutions. Since

$$\gcd(180,105)=15$$

and $15\mid 30$, the equation is solvable.

Using the extended Euclidean algorithm,

$$15=180\cdot3-105\cdot5.$$

Multiplying by $2$ gives

$$30=180\cdot6-105\cdot10.$$

So one solution is $(x,y)=(6,-10)$. Since $a/d=12$ and $b/d=7$, all solutions are

$$(x,y)=(6+7k,-10-12k),\qquad k\in\mathbb Z.$$

In the measuring interpretation, positive coefficients count additions to the bucket and negative coefficients count removals. Fill with six cups of $180$ mL, then remove ten glasses of $105$ mL. The bucket holds $1080-1050=30$ mL; an integer solution does not require both coefficients to be nonnegative.

Quick checks

Checkpoint

What does $a\mid b$ mean in integer language?

Use the quantifier hidden in the definition.

Solution · Answer

It means that there exists an integer $d$ such that $b=ad$.

Checkpoint

Why does every common divisor of $a$ and $b$ divide every expression $ax+by$ with $x,y\in\mathbb Z$?

Use the definition of divisibility twice.

Solution · Answer

If $n\mid a$ and $n\mid b$, then $a=nr$ and $b=ns$ for some integers $r,s$. Thus $ax+by=n(rx+sy)$, and $rx+sy$ is an integer.

Checkpoint

In the Euclidean algorithm for $7224$ and $1290$, why is the gcd the last nonzero remainder?

Use the identity $\gcd(a,b)=\gcd(b,r)$ after each division step.

Solution · Answer

Each division step preserves the gcd, so the original gcd equals the gcd of the last nonzero remainder $258$ and $0$. That gcd is $258$.

Checkpoint

What condition decides whether $ax+by=c$ has integer solutions?

State it using $\gcd(a,b)$.

Solution · Answer

The equation has integer solutions if and only if $\gcd(a,b)\mid c$.

Exercises

1. List all positive divisors of $84$, and compute $\gcd(84,60)$.
2. Use the division algorithm to write $-37=5q+r$ with $0\le r\lt5$.
3. Use the Euclidean algorithm to compute $\gcd(252,198)$.
4. Express $\gcd(252,198)$ as $252x+198y$.
5. Prove that if $n\mid a$ and $n\mid b$, then $n\mid\gcd(a,b)$.
6. Determine whether $35x+21y=14$ has integer solutions. If it does, find one.
7. Determine whether $35x+21y=10$ has integer solutions.
8. Use prime factorizations to compute $\gcd(2^4\cdot3^2\cdot5,\, 2^3\cdot3^5\cdot7)$.

Solution · Model solution 1

The positive divisors of $84$ are $1,2,3,4,6,7,12,14,21,28,42,84$. Since $60=2^2\cdot3\cdot5$ and $84=2^2\cdot3\cdot7$, $\gcd(84,60)=2^2\cdot3=12$.

Solution · Model solution 2

We need a remainder between $0$ and $4$. Since $-37=5(-8)+3$, the quotient is $q=-8$ and the remainder is $r=3$.

Solution · Model solution 3

$252=198\cdot1+54$, $198=54\cdot3+36$, $54=36\cdot1+18$, and $36=18\cdot2+0$. Hence $\gcd(252,198)=18$.

Solution · Model solution 4

Back-substitute: $18=54-36=54-(198-3\cdot54)=4\cdot54-198$. Since $54=252-198$, we get $18=4(252-198)-198=4\cdot252-5\cdot198$.

Solution · Model solution 5

By Bézout's identity, $\gcd(a,b)=ax+by$ for some integers $x,y$. If $n$ divides both $a$ and $b$, then $n$ divides the right-hand side.

Solution · Model solution 6

$\gcd(35,21)=7$, and $7\mid14$, so solutions exist. The direct check $35(1)+21(-1)=14$ gives $(x,y)=(1,-1)$ as one solution. All solutions are $(1+3k,-1-5k)$ for integer $k$, since $35/7=5$ and $21/7=3$.

Solution · Model solution 7

$\gcd(35,21)=7$, but $7\nmid10$, so there are no integer solutions.

Solution · Model solution 8

Compare the smaller exponent of each prime: $2^{\min(4,3)}3^{\min(2,5)}5^{\min(1,0)}7^{\min(0,1)} =2^3\cdot3^2=72$.