Week 1 - Day 3: Divisibility

In this class session, we delve into the concept of divisibility and its properties. We'll explore the definition of divisibility, examine key properties, and work through specific examples and proofs. By the end of this session, you'll have a solid understanding of how divisibility operates within the integers, particularly the divisibility rules for certain numbers.

Divisibility

Definition: Let \(a, b \in \mathbb{Z}\) with \(b \neq 0\). We say that \(b\) divides \(a\), written as \(b \mid a\), if there exists an integer \(q\) such that:

\[ a = bq \quad \text{for some} \quad q \in \mathbb{Z}. \]

This means that \(b\) is a factor of \(a\), or equivalently, \(a\) is a multiple of \(b\). Another way to think of it is that when \(a\) is divided by \(b\), the remainder is 0.

Synonyms and Notation

  • \(b\) divides \(a\)
  • \(a\) is a multiple of \(b\)
  • If \(b \mid a\) is false, we write \(b \nmid a\).

Example: A Common Misunderstanding

Let's clarify a common misunderstanding between division and divisibility statements. For instance:

\[ 6 / 3 = 2 \]

This operation is a division, but the statement \(6 \mid 3\) is false because no integer \(q\) satisfies \(6 = 3q\). However, \(3 \mid 6\) is true since 6 is divisible by 3 with \(q = 2\).

Common Properties of Divisibility

Now, let's explore some important properties related to divisibility. For all \(a, b, c \in \mathbb{Z}\), the following properties hold:

  1. If \(a \mid b\) and \(a \mid c\), then \(a \mid (b + c)\).
  2. More generally, if \(a \mid b\) and \(a \mid c\), then \(a \mid (br + cs)\) for all integers \(r, s \in \mathbb{Z}\).

This second property is known as the \(\mathbb{Z}\)-linear combination of \(b\) and \(c\), which means any integer combination of \(b\) and \(c\) is still divisible by \(a\) if both \(b\) and \(c\) are divisible by \(a\).

Examples of Linear Combinations

For example, if \(a \mid b\) and \(a \mid c\), then \(a\) divides combinations like:

  • \(2b + 7c\)
  • \(-3b + 0c\)
  • \(5b - 11c\)

Proof Outline: Property (1)

We can also outline a proof of the first property, where \(a \mid b\) and \(a \mid c\) implies \(a \mid (b + c)\).

  1. Assume \(a \mid b\) and \(a \mid c\).
  2. By the definition of divisibility, there exist integers \(q_1\) and \(q_2\) such that:
    3. \[ b = aq_1 \quad \text{and} \quad c = aq_2. \]
  3. Now, consider the sum \(b + c\):
    4. \[ b + c = aq_1 + aq_2 = a(q_1 + q_2). \]
  4. Since \(b + c\) is a multiple of \(a\), it follows that \(a \mid (b + c)\). \( \blacksquare \)

Transitivity of Divisibility

The property of transitivity also applies here. If \(a \mid b\) and \(b \mid c\), then \(a \mid c\). This property behaves similarly to equality: if \(a = b\) and \(b = c\), then \(a = c\).

Counterexample for Inequality

However, transitivity does not apply to inequalities. For example:

  • If \(2 \neq 1\) and \(2 \neq 1\), this would not imply that \(1 \neq 1\), so transitivity fails for inequalities.

True/False Statements on Divisibility

Next, let's review a few divisibility statements, discussing whether they hold true or false:

  • \(a \mid b\) or \(a \mid c \Rightarrow a \mid bc\)
  • \(a \mid bc \Rightarrow a \mid b\) or \(a \mid c\)
  • \(a \mid c\) and \(b \mid c \Rightarrow ab \mid c\)

Each of these properties requires careful proof or counterexamples to verify their truth.

Divisibility by 3

Another important divisibility rule we cover is divisibility by 3. One result we establish is:

Theorem

An integer is divisible by 3 if and only if the sum of its digits is divisible by 3. For example:

\[ 3 \mid 1,002,001,002,000. \]

Proof by Induction: Divisibility by 3

We can also prove that \(3 \mid (10^i - 1)\) using induction, which is a familiar proof technique:

\[ 10^i - 1 = 999...999 = 3 \times (333...333). \]

Induction confirms this result for all \(i \in \mathbb{N}\).

Divisibility Through Decimal Expansions

Another key concept is divisibility by 3 via decimal expansions. Consider a number \(n\) with decimal expansion:

\[ N = d_k d_{k-1} \dots d_1 d_0, \]

where \(d_i\) are the digits. The theorem states that \(n\) is divisible by 3 if and only if the sum of its digits is divisible by 3.

Example: Divisibility in Action

Let’s apply this rule to a number like 123. The sum of its digits is:

\[ 1 + 2 + 3 = 6, \]

Since 6 is divisible by 3, we conclude that 123 is divisible by 3.

Conclusion

Understanding divisibility, especially rules like divisibility by 3, forms the basis for deeper studies in number theory. As you work through the homework, be sure to practice proving these properties and applying the rules to different scenarios.

Sample Problem: Divisibility by 3

Let’s wrap up with one final example:

\[ \text{Is } 598,234 \text{ divisible by 3}? \]

First, sum the digits: \(5 + 9 + 8 + 2 + 3 + 4 = 31\). Since 31 is not divisible by 3, we conclude that 598,234 is not divisible by 3.