3.2 Divisibility

Concept of divisibility

Divisibility is about whether one integer divides another evenly, with no remainder left over. It's one of the most fundamental ideas in number theory, and it shows up constantly in proofs, problem-solving, and even applied fields like cryptography.

Definition and notation

The notation $a \mid b$ reads as "a divides b" (or equivalently, "b is divisible by a"). The formal definition: $a \mid b$ if there exists an integer $k$ such that $b = ak$.

For example, $3 \mid 12$ because $12 = 3 \times 4$. But $5 \nmid 12$ because no integer $k$ satisfies $12 = 5k$.

A few things to keep straight:

• Divisibility is defined on integers only, not fractions or irrational numbers
• The divider ($a$) comes first in the notation $a \mid b$, which trips people up. Think of the vertical bar as saying "goes into"
• $a \mid b$ is a statement that's either true or false. It's not a number or an operation

Divisibility rules

These are shortcuts that let you check divisibility without doing long division. The most common ones:

• By 2: The last digit is even (0, 2, 4, 6, or 8)
• By 3: Add up all the digits. If that sum is divisible by 3, so is the original number. For example, 471 → 4 + 7 + 1 = 12, and $3 \mid 12$, so $3 \mid 471$
• By 4: The last two digits form a number divisible by 4
• By 5: The last digit is 0 or 5
• By 6: The number passes both the test for 2 and the test for 3
• By 8: The last three digits form a number divisible by 8
• By 9: Same idea as the rule for 3, but the digit sum must be divisible by 9

Factors and multiples

Factors of a number are the integers that divide it evenly. Multiples of a number are what you get when you multiply it by any integer.

For 12: its factors are 1, 2, 3, 4, 6, and 12. Its multiples are 12, 24, 36, 48, and so on.

• Every positive integer has at least two factors: 1 and itself
• Prime numbers have exactly two factors (1 and themselves). Examples: 2, 3, 5, 7, 11
• Composite numbers have more than two factors. Examples: 4, 6, 9, 15
• The number 1 is neither prime nor composite

Properties of divisibility

These properties let you build chains of reasoning about which numbers divide which. They're essential tools for writing proofs in number theory.

Transitive property

If $a \mid b$ and $b \mid c$, then $a \mid c$.

Written formally: $(a \mid b) \land (b \mid c) \Rightarrow (a \mid c)$

For example, $3 \mid 6$ and $6 \mid 24$, so $3 \mid 24$. This lets you build longer chains of divisibility without checking each link from scratch.

Divisibility and linear combinations

If $a \mid b$ and $a \mid c$, then $a$ divides any linear combination of $b$ and $c$. That means $a \mid (bx + cy)$ for any integers $x$ and $y$.

As a special case, the sum or difference of two multiples of $a$ is also a multiple of $a$. For instance, since $4 \mid 20$ and $4 \mid 12$, you know $4 \mid (20 + 12) = 32$ and $4 \mid (20 - 12) = 8$.

Divisibility by products

Here's a property that requires a condition people often forget: if $a \mid n$ and $b \mid n$, then $ab \mid n$ only when $a$ and $b$ are coprime (meaning $\gcd(a, b) = 1$).

For example, $2 \mid 12$ and $3 \mid 12$, and since $\gcd(2, 3) = 1$, you can conclude $6 \mid 12$. But $2 \mid 12$ and $4 \mid 12$ does not let you conclude $8 \mid 12$, because $\gcd(2, 4) = 2 \neq 1$.

Prime numbers and divisibility

Primes are the building blocks of all integers. Every number theory argument about divisibility eventually comes back to primes.

Prime factorization

Prime factorization means breaking a number down into a product of primes. Here's the process:

1. Start with the smallest prime (2). If it divides your number, divide and record it
2. Keep dividing by that prime until it no longer goes in evenly
3. Move to the next prime (3, then 5, then 7...) and repeat
4. Stop when you reach 1

For example, to factor 360: $360 = 2 \times 180 = 2^2 \times 90 = 2^3 \times 45 = 2^3 \times 3 \times 15 = 2^3 \times 3^2 \times 5$

Once you have the prime factorization, you can read off every factor of the number by choosing different combinations of those prime powers.

Fundamental theorem of arithmetic

Every integer greater than 1 is either prime or can be expressed as a unique product of primes (up to the order of the factors).

This uniqueness is the key part. It means 12 is always $2^2 \times 3$, no matter how you go about factoring it. Without this guarantee, much of number theory would fall apart, because you couldn't make reliable arguments about a number's divisibility properties from its factorization.

Greatest common divisor

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them.

Two ways to find it:

• Prime factorization method: Factor both numbers, then take the lowest power of each shared prime. For $\gcd(36, 48)$: $36 = 2^2 \times 3^2$ and $48 = 2^4 \times 3$, so $\gcd(36, 48) = 2^2 \times 3 = 12$
• Euclidean algorithm: Repeatedly apply the division algorithm. To find $\gcd(48, 36)$: $48 = 1 \times 36 + 12$, then $36 = 3 \times 12 + 0$. The last nonzero remainder is 12, so $\gcd(48, 36) = 12$

Two numbers are coprime (or relatively prime) when $\gcd(a, b) = 1$. For instance, 8 and 15 are coprime even though neither is prime.

The GCD is also crucial for solving linear Diophantine equations of the form $ax + by = c$, which have integer solutions only when $\gcd(a, b) \mid c$.

Applications of divisibility

Number theory problems

Divisibility is central to most number theory problems you'll encounter. It's used in:

• Proving properties of integers (e.g., "the product of any three consecutive integers is divisible by 6")
• Solving Diophantine equations and congruences
• Analyzing patterns in integer sequences
• Establishing when equations have or don't have integer solutions

Cryptography basics

Modern encryption leans heavily on divisibility and prime factorization. RSA encryption, one of the most widely used systems, relies on a simple asymmetry: multiplying two large primes together is fast, but factoring the result back into those primes is extraordinarily slow for large numbers.

Modular arithmetic, which is built directly on divisibility, underpins most cryptographic protocols.

Calendar systems

The Gregorian calendar's leap year rule is a neat real-world example of divisibility:

1. A year is a leap year if it's divisible by 4
2. Unless it's also divisible by 100, in which case it's not
3. Unless it's also divisible by 400, in which case it is

So 2000 was a leap year (divisible by 400), but 1900 was not (divisible by 100 but not 400), and 2024 is (divisible by 4 but not 100).

Divisibility tests

Common divisibility tests

Beyond the basic rules covered earlier, here are a couple more:

• By 11: Take the alternating sum of digits (subtract, add, subtract...). If the result is divisible by 11, so is the original. For 9174: $9 - 1 + 7 - 4 = 11$, and $11 \mid 11$, so $11 \mid 9174$

Why divisibility tests work

These tests aren't magic. They follow from properties of powers of 10 in modular arithmetic.

Consider the test for 3. Any number can be written as a sum of its digits times powers of 10. Since $10 \equiv 1 \pmod{3}$, every power of 10 is also $\equiv 1 \pmod{3}$. So the number has the same remainder as the sum of its digits when divided by 3.

The test for 11 works similarly: $10 \equiv -1 \pmod{11}$, so powers of 10 alternate between $+1$ and $-1$ mod 11, which is why you take an alternating sum.

Creating new divisibility tests

You can build new tests using modular arithmetic:

• Tests for composite numbers can sometimes be constructed by combining tests for coprime factors (e.g., the test for 6 combines tests for 2 and 3)
• Tests for primes like 7 or 13 exist but are more involved, often using properties of how powers of 10 cycle modulo those primes

Divisibility in algebraic structures

Divisibility extends beyond integers into other algebraic settings, which is where the "abstract algebra" part of this unit comes in.

Polynomials and divisibility

Polynomial divisibility works much like integer divisibility. You say $f(x) \mid g(x)$ if there's a polynomial $q(x)$ such that $g(x) = f(x) \cdot q(x)$.

Two key theorems connect roots and divisibility:

• Remainder Theorem: When you divide $f(x)$ by $(x - c)$, the remainder is $f(c)$
• Factor Theorem: $(x - c) \mid f(x)$ if and only if $f(c) = 0$. In other words, $c$ is a root exactly when $(x - c)$ is a factor

Polynomial long division (or synthetic division) is the tool you use to carry out these divisions.

Modular arithmetic

In modular arithmetic, numbers "wrap around" after reaching a fixed value called the modulus. The notation $a \equiv b \pmod{m}$ means that $m \mid (a - b)$.

For example, $17 \equiv 2 \pmod{5}$ because $5 \mid (17 - 2) = 15$.

Modular arithmetic preserves addition, subtraction, and multiplication. If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$ and $ac \equiv bd \pmod{m}$.

This system is the foundation for the Chinese Remainder Theorem, which lets you solve systems of simultaneous congruences.

Congruence relations

A congruence relation $a \equiv b \pmod{n}$ is really a statement about divisibility: $n \mid (a - b)$. Congruences behave a lot like equations. You can add, subtract, and multiply both sides. Division is trickier and only works under certain conditions (the divisor must be coprime to the modulus).

Congruences are used extensively in number theory proofs and in cryptographic algorithms.

Advanced divisibility concepts

Diophantine equations

Diophantine equations are polynomial equations where you only care about integer solutions. The simplest type is the linear Diophantine equation $ax + by = c$.

The key result: $ax + by = c$ has integer solutions if and only if $\gcd(a, b) \mid c$. When solutions exist, you can find them using the extended Euclidean algorithm, and there are infinitely many solutions.

More complex Diophantine equations (like Pell's equation $x^2 - Dy^2 = 1$) require more advanced techniques but still rely on divisibility ideas at their core.

Divisibility sequences

A divisibility sequence is a sequence where $a_m \mid a_n$ whenever $m \mid n$. The Fibonacci sequence has this property: $F_m \mid F_n$ whenever $m \mid n$. For instance, $F_3 = 2$ divides $F_6 = 8$, and $F_4 = 3$ divides $F_8 = 21$.

These sequences connect divisibility to recurrence relations and reveal surprising structure in familiar sequences.

Perfect, deficient, and abundant numbers

Classifying numbers by the sum of their proper divisors gives three categories:

• Perfect numbers: The sum of proper divisors equals the number. Examples: $6 = 1 + 2 + 3$, $28 = 1 + 2 + 4 + 7 + 14$
• Deficient numbers: The sum of proper divisors is less than the number (e.g., 8, where $1 + 2 + 4 = 7 < 8$)
• Abundant numbers: The sum of proper divisors exceeds the number (e.g., 12, where $1 + 2 + 3 + 4 + 6 = 16 > 12$)

All known perfect numbers are even. Whether an odd perfect number exists remains one of the oldest open problems in mathematics.

Historical perspectives

Ancient divisibility methods

Divisibility concepts are ancient. The Babylonians used them in their base-60 number system (which is why we have 60 seconds in a minute). Greek mathematicians, especially Euclid, studied perfect numbers and formalized prime factorization. The Chinese Remainder Theorem, one of the earliest results connecting systems of divisibility conditions, dates back to the 3rd century CE.

Famous mathematicians and divisibility

• Euclid (c. 300 BCE) formalized divisibility in his Elements, including a proof that there are infinitely many primes
• Fermat (1600s) advanced number theory with results like Fermat's Little Theorem, which connects divisibility to modular exponentiation
• Euler (1700s) introduced the totient function $\phi(n)$, which counts integers less than $n$ that are coprime to $n$
• Gauss (1801) published Disquisitiones Arithmeticae, which systematized modular arithmetic and transformed number theory into a rigorous discipline