Foundational Concepts of Divisibility and Number Theory

TL;DR

Divisibility is about whether one whole number perfectly divides another without a remainder, a core idea in number theory. We'll explore integers, factors, multiples, and the division algorithm. Understanding these basics is crucial for working with more complex divisibility rules later on.

1. The Mental Model

Imagine you have a stack of items. Divisibility just asks if you can arrange that stack into perfectly equal smaller stacks, with nothing left over. If you can, one number divides the other.

2. The Core Material

Divisibility is a fundamental concept in number theory, which is the study of integers and their properties. Before diving into divisibility rules for composite numbers, let's make sure we're clear on the basics.

What are Integers?

Photo by Katerina Holmes on Pexels

Integers are simply all whole numbers, both positive and negative, including zero. Think of them as ..., -3, -2, -1, 0, 1, 2, 3, .... When we talk about divisibility, we're usually talking about dividing one integer by another, and the result being an integer without a fractional part.

Divisibility Defined

Photo by Ferdous Hasan on Pexels

We say an integer a divides an integer b (written as a | b) if there's another integer k such that b = a * k.
If a divides b, then:
* a is a factor or divisor of b.
* b is a multiple of a.

For example, 3 | 12 because 12 = 3 * 4. Here, 3 is a factor of 12, and 12 is a multiple of 3.

The Division Algorithm (Euclidean Division)

Photo by Jakub Zerdzicki on Pexels

This isn't an algorithm in the sense of a step-by-step computer program, but rather a theorem. It states that for any integer a (the dividend) and any non-zero integer b (the divisor), there exist unique integers q (the quotient) and r (the remainder) such that:

a = bq + r

where 0 ≤ r < |b|.

The remainder r is super important. If r = 0, then b divides a perfectly. If r ≠ 0, then b does not divide a.

Let's look at the relationship between these concepts:

graph TD
    A["Integer 'a' (Dividend)"]
    B["Integer 'b' (Divisor ≠ 0)"]
    C["Integer 'q' (Quotient)"]
    D["Integer 'r' (Remainder)"]
    E["a is divisible by b (b | a)"]
    F["a is NOT divisible by b"]

    A & B --> G["Perform Division Algorithm: a = bq + r"]
    G --> H{Is r = 0?}
    H -- Yes --> E
    H -- No --> F
    E --> I["b is a Factor of a"]
    E --> J["a is a Multiple of b"]
    F --> K["r is the 'leftover'"]

Properties of Divisibility

Photo by Philippe WEICKMANN on Pexels

Here are some useful properties:
* Transitivity: If a | b and b | c, then a | c. (e.g., if 2 divides 4, and 4 divides 12, then 2 divides 12).
* Linear Combination: If a | b and a | c, then a | (bx + cy) for any integers x and y. (e.g., if 3 divides 6 and 3 divides 9, then 3 divides (6*2 + 9*1) = 12 + 9 = 21).
* Identity: 1 | a for any integer a. (1 divides everything).
* Zero: a | 0 for any non-zero integer a. (Any non-zero number divides 0, because 0 = a * 0).
* Self: a | a for any non-zero integer a.

3. Worked Example

Let's use the division algorithm to determine if 7 divides 53.

1. Identify a and b: Here, a = 53 (dividend) and b = 7 (divisor).
2. Perform division: We need to find q and r such that 53 = 7q + r where 0 ≤ r < 7.
3. Calculate quotient: How many times does 7 go into 53 without exceeding it? 7 * 7 = 49, and 7 * 8 = 56. So, q = 7.
4. Calculate remainder: r = a - bq = 53 - (7 * 7) = 53 - 49 = 4.
5. Check remainder: Since r = 4, and 4 ≠ 0, 7 does not divide 53.
   • 7 is not a factor of 53.
   • 53 is not a multiple of 7.

4. Key Takeaways

• Integers are whole numbers, including zero and negative numbers.
• a divides b (a | b) if b can be written as a times some other integer.
• The Division Algorithm a = bq + r shows that b | a if and only if the remainder r is zero.
• A factor (or divisor) is a number that divides another number perfectly.
• A multiple is a number that can be divided perfectly by another number.
• Divisibility properties (like transitivity) help simplify reasoning about numbers.

Common Mistakes to Avoid:
- Confusing "divides" with "is divided by." "3 divides 12" means 12 / 3, not 3 / 12.
- Forgetting that 0 is divisible by any non-zero integer.
- Assuming a remainder of 1 means it's "almost" divisible; it's still not divisible.
- Trying to divide by zero; this is undefined.
- Not checking that the remainder r is always less than the absolute value of the divisor |b|.

5. Now Try It

Choose two random integers, a and b (where b is not zero). Use the division algorithm to find the quotient q and remainder r. Then, state whether b divides a based on your result. Repeat this process three times with different pairs of integers. Success means you can consistently and correctly identify q, r, and the divisibility status for each pair.