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

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.

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.

Primes, composites, and well-ordering

Equivalently, $n>1$ is composite exactly when

$$n=n_1n_2$$

for integers $n_1,n_2$ satisfying $1<n_1,n_2<n$.

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

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.

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<n_1,n_2<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.

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

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.

The gcd removes the common part of two integers. If

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

then

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

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.

The condition $0\le r<|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.

Gcd invariance and the Euclidean algorithm

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

Indeed, a common divisor of a and b divides $r=a-bq$, and a common divisor of b and r divides $a=bq+r$. Therefore the two pairs have exactly the same positive common divisors.

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 Bezout's identity

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

This result says that the gcd is not merely the largest common divisor; it is also the smallest positive integer that can be built as an integer linear combination of a and b.

One direction is Bezout'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.

Common divisors and Euclid's lemma

Bezout's identity also gives a cleaner characterization of the gcd.

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 Bezout combination equal to $\gcd(a,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$.

Unique prime factorization

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.

The theorem lets us compute gcds by comparing 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)}.$$

Linear Diophantine equations

An equation

$$ax+by=c$$

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

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

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

Thus (mr,nr) is a solution.

Once one solution is known, all solutions can be described. Suppose $d=\gcd(a,b)\ne0$, 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.$$

Quick checks

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<5$.
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)$.