Properties of Divisibility

Greetings! In our last lesson, we explored the Division Algorithm, not as a method of calculation, but as a theorem guaranteeing the unique structure of integers. We saw how it partitions the set of all integers $Z$ based on their remainder when divided by a positive integer $d$ . Today, we build directly on that foundation.

This lesson focuses on the special case where the remainder is zero. This simple condition gives rise to the concept of divisibility, a cornerstone of number theory. We will formally define what it means for one integer to divide another and then, crucially, prove the fundamental properties that govern this relationship. These properties—especially transitivity and linearity—are the grammatical rules of the language of number theory. Mastering them will allow us to construct rigorous arguments about the relationships between integers.

1. The Formal Definition of Divisibility

In the context of the Division Algorithm, $a = q d + r$ , when we say that $d$ divides $a$ , we are simply stating that the remainder $r$ is 0. This leads to a more direct definition.

Let's watch a short video segment that lays out this formal definition and provides a few clear examples.

To summarize and formalize the definition:

Let $a$ and $b$ be integers with $a \neq = 0$ . We say that $a$ divides $b$ , and we write $a ∣ b$ , if there exists an integer $k$ such that $b = ak$ .

If $a ∣ b$ , we can also say that:

$a$ is a divisor or factor of $b$ .
$b$ is a multiple of $a$ .

A few important details to note:

The divisor $a$ cannot be zero. Division by zero is undefined.
The dividend $b$ can be any integer. For example, for any non-zero integer $a$ , we have $a ∣0$ because we can write $0 = a \cdot 0$ , where $k = 0$ is a valid integer.
The integer $k$ can be positive, negative, or zero. For instance, $3∣ (- 12)$ because $- 12 = 3 \cdot (- 4)$ .

2. The Fundamental Properties of Divisibility

Now that we have a precise definition, we can use it to prove the properties that make divisibility such a powerful concept. These properties might seem obvious at first glance, but proving them rigorously from the definition is an essential exercise in mathematical thinking. It’s the process of transforming intuition into logical certainty.

The two most critical properties are transitivity and linearity.

Transitivity

This property states that if an integer $a$ divides an integer $b$ , and $b$ in turn divides a third integer $c$ , then $a$ must also divide $c$ . This establishes a chain-like relationship.

Linearity

This property is perhaps the most powerful tool in elementary number theory. It states that if an integer $a$ divides two other integers, $b$ and $c$ , then it must also divide any integer linear combination of them. An integer linear combination of $b$ and $c$ is any expression of the form $mb + n c$ , where $m$ and $n$ are integers.

The following resource formally states and proves these two properties. Your task is to carefully read and understand the logic of these proofs.

1 Integers and Divisibility

This document from Jay Daigle's number theory notes provides concise, formal proofs for the properties we are studying. Getting comfortable with this style of mathematical writing is a key part of your goal.

First, review the definition to see how it matches what we've discussed. Next, read the proof of transitivity in Lemma 1.11. Notice how it starts by assuming the premises (a|b and b|c), translates them using the definition of divisibility, performs a simple algebraic substitution, and then translates the result back using the definition to reach the conclusion. Finally, read the proof of the Linear Combinations property in Lemma 1.13. This proof follows the exact same pattern: assume, translate, manipulate, conclude. This is the fundamental structure of most proofs you will encounter.

To make the linearity property concrete, consider this example:
We know that $4∣20$ and $4∣36$ . The linearity property guarantees that $4$ must divide any number of the form $20 m + 36 n$ .
Let's pick $m = 3$ and $n = - 2$ .
Then we have $20 (3) + 36 (- 2) = 60 - 72 = - 12$ . And indeed, $4∣ (- 12)$ , since $- 12 = 4 \cdot (- 3)$ . This property holds for any integers $m$ and $n$ you could choose.

3. A Few More Useful Properties

Besides transitivity and linearity, there are several other straightforward properties that are useful to know. Let's prove one together and then list a few others.

Property: If $a ∣ b$ and $a, b$ are positive integers, then $a \leq b$ .

Proof:

From the premise $a ∣ b$ , our definition tells us there is an integer $k$ such that $b = ak$ .
Since $a$ and $b$ are both positive, the integer $k$ must also be positive.
Because $k$ is a positive integer, it must be at least 1, so $k \geq 1$ .
Multiplying this inequality by the positive integer $a$ gives us $ak \geq a$ .
Since $b = ak$ , we can substitute to get $b \geq a$ , which is the same as $a \leq b$ .

This is a simple but elegant argument that relies only on the definition of divisibility and basic properties of inequalities. Here are a few others, which you can try proving yourself using the same method:

Multiplication Property: If $a ∣ b$ , then $a ∣ b c$ for any integer $c$ .
(Hint: If $b = ak$ , what is $b c$ ?)
Cancellation Property: If $c \neq = 0$ , then $a ∣ b$ if and only if $c a ∣ c b$ .
(Hint: This is a two-way street; you have to prove it in both directions.)
Magnitude Property: If $a ∣ b$ and $b \neq = 0$ , then $∣ a ∣ \leq ∣ b ∣$ .
(This is a generalization of the property we just proved for positive integers.)

These properties form our basic toolkit for manipulating expressions involving divisibility. We will use them implicitly and explicitly in almost every topic that follows.

Conclusion

In this lesson, we have moved from the general structure of the Division Algorithm to the specific, crucial relationship of divisibility.

Key Takeaways:

Divisibility ( $a ∣ b$ ) is formally defined by the existence of an integer $k$ such that $b = ak$ , where $a \neq = 0$ .
The proof of any property of divisibility starts by applying this definition to the assumptions.
Transitivity ( $a ∣ b$ and $b ∣ c ⟹ a ∣ c$ ) establishes a chain of divisibility.
Linearity ( $a ∣ b$ and $a ∣ c ⟹ a ∣ (mb + n c)$ ) is a powerful tool that shows divisibility is preserved under linear combinations.

You've now established the foundational rules of engagement for number theory. In our next lesson, we will use these rules to tackle a classic problem: given two integers, what is their greatest common divisor (GCD)? We will see that this question is not just about finding a number, but about uncovering a deeper structural relationship between the two integers, a relationship that the linearity property will help us to fully understand.

Recommended resources