Divisibility and Primes - Key Properties

The theory of divisibility reveals deep structural properties of the integers. Two fundamental results, the Division Algorithm and Bézout's Identity, provide the foundation for many subsequent developments in number theory.

TheoremDivision Algorithm

Let $a, b \in \mathbb{Z}$ with $b > 0$ . Then there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $a = bq + r, \quad 0 \leq r < b$

The quotient $q$ is often written as $\lfloor a/b \rfloor$ , and the remainder $r$ as $a \bmod b$ .

The Division Algorithm is remarkable in guaranteeing both existence and uniqueness of the quotient and remainder. This uniqueness is crucial for the well-definedness of the remainder operation, which appears throughout number theory.

ExampleDivision Algorithm in Action

Consider $a = 17$ and $b = 5$ . Then: $17 = 5 \cdot 3 + 2$

Here $q = 3$ and $r = 2$ . Note that $0 \leq 2 < 5$ as required.

For negative dividends, say $a = -17$ and $b = 5$ : $-17 = 5 \cdot (-4) + 3$

We have $q = -4$ and $r = 3$ . The remainder must satisfy $0 \leq r < b$ , so $r$ cannot be $-2$ .

TheoremBézout's Identity

Let $a, b \in \mathbb{Z}$ , not both zero, and let $d = \gcd(a, b)$ . Then there exist integers $x, y$ such that: $ax + by = d$

Moreover, $d$ is the smallest positive integer that can be expressed in the form $ax + by$ with $x, y \in \mathbb{Z}$ .

Bézout's Identity is fundamental because it expresses the greatest common divisor as a linear combination of the original numbers. The coefficients $x$ and $y$ are called Bézout coefficients and can be computed using the Extended Euclidean Algorithm.

Remark

An important consequence of Bézout's Identity: if $\gcd(a, b) = 1$ , then there exist integers $x, y$ such that $ax + by = 1$ . This fact is crucial in solving linear Diophantine equations and in the construction of modular inverses.

ExampleBézout Coefficients

Let $a = 35$ and $b = 14$ . We have $\gcd(35, 14) = 7$ . We can verify: $35 \cdot (-1) + 14 \cdot 3 = -35 + 42 = 7$

Thus, $x = -1$ and $y = 3$ are Bézout coefficients. Note that these coefficients are not unique: we could also write $7 = 35 \cdot 1 + 14 \cdot (-2)$ .

The Euclidean algorithm systematically produces these coefficients by working backwards through the sequence of remainders generated during the gcd computation.