Divisibility

Divisibility, in the grand, often tedious, scheme of number theory , is the notion of whether one integer can be divided by another integer without leaving a remainder. Thrilling, I know. It’s the mathematical equivalent of checking if your leftovers will fit into a slightly smaller container. You’re looking for a perfect fit, no awkward overhangs, no forced squeezes. If an integer $a$ can be divided by a non-zero integer $b$ such that the result is another integer, then $a$ is said to be divisible by $b$. This is often expressed as $b \mid a$, which, in plain English, means $b$ is a divisor or a factor of $a$, and $a$ is a multiple of $b$. It’s a relationship, really. Like a very specific, rather unforgiving, social hierarchy among numbers.

Definition and Notation

Let’s get down to brass tacks, shall we? For any two integers, $a$ and $b$, where $b \neq 0$, we say that $b$ divides $a$ (or $a$ is divisible by $b$) if there exists an integer $c$ such that $a = bc$. The notation for this, as I’ve already alluded to, is $b \mid a$. Conversely, if no such integer $c$ exists, then $b$ does not divide $a$, denoted as $b \nmid a$.

Consider the number 10. It’s divisible by 2 because $10 = 2 \times 5$, and 5 is an integer. So, $2 \mid 10$. It’s also divisible by 5, because $10 = 5 \times 2$, and 2 is an integer. Hence, $5 \mid 10$. And, of course, it’s divisible by 1 and 10 itself, because $10 = 1 \times 10$ and $10 = 10 \times 1$. These are the trivial divisors. The non-trivial ones – the ones that actually make things interesting – are 2 and 5.

Now, 10 is not divisible by 3. There’s no integer $c$ that you can multiply by 3 to get 10. You’d get $10/3 = 3.333…$, which is decidedly not an integer. So, $3 \nmid 10$. This is where the concept of a remainder comes into play. When you divide 10 by 3, you get a quotient of 3 and a remainder of 1. The remainder is the leftover bit, the mathematical equivalent of dust bunnies under the sofa. For divisibility, that remainder must be zero. The Division Algorithm formalizes this, stating that for any integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$, where $0 \le r < b$. Divisibility by $b$ occurs precisely when $r=0$.

Properties of Divisibility

Like any good social construct, divisibility comes with its own set of rules and predictable behaviors. These properties make navigating the murky waters of number theory slightly less treacherous, though no less tiresome.

• Reflexivity: Every integer is divisible by itself. Yes, even your questionable life choices. For any integer $a$, $a \mid a$, because $a = a \times 1$. This is the mathematical equivalent of narcissism.
• Transitivity: If $a$ divides $b$, and $b$ divides $c$, then $a$ must divide $c$. Think of it as a chain reaction of divisibility. If $a \mid b$, then $b = ak$ for some integer $k$. If $b \mid c$, then $c = bl$ for some integer $l$. Substituting the first into the second, we get $c = (ak)l = a(kl)$. Since $k$ and $l$ are integers, their product $kl$ is also an integer. Thus, $a \mid c$. This property is fundamental in understanding relationships between divisors, much like understanding how your friends’ opinions can influence your own.
• Non-negativity of Divisor: If $b \mid a$ and $a \neq 0$, then $|b| \le |a|$. This means that a non-zero number cannot be divisible by a number strictly larger than itself in absolute value. It’s like trying to fit a whale into a teacup. The divisor must be smaller than or equal to the dividend (if the dividend isn’t zero).
• Zero as a Multiple: For any integer $a$, $a \mid 0$. This is because $0 = a \times 0$, and 0 is an integer. So, zero is divisible by everything, except itself, which is a whole other philosophical debate for set theory .
• Sum and Difference: If $a \mid b$ and $a \mid c$, then $a \mid (b+c)$ and $a \mid (b-c)$. This is a rather useful property, allowing us to combine divisible quantities. If $b = ak$ and $c = al$ for some integers $k$ and $l$, then $b+c = ak + al = a(k+l)$ and $b-c = ak - al = a(k-l)$. Since $k+l$ and $k-l$ are integers, $a$ divides both their sum and difference. This is the bedrock of many modular arithmetic operations.
• Multiples: If $a \mid b$, then $a \mid bc$ for any integer $c$. If $b = ak$, then $bc = (ak)c = a(kc)$. Since $kc$ is an integer, $a \mid bc$. This means that if a number divides another, it also divides any multiple of that number.

These properties might seem elementary, but they are the building blocks for more complex ideas in number theory, such as prime numbers and greatest common divisors .

Divisibility Rules

While the formal definition of divisibility involves performing the division, there are handy shortcuts, known as divisibility rules, that allow us to determine if a number is divisible by another without actually doing the long division. These are particularly useful for small divisors and are often taught to schoolchildren as a way to avoid the drudgery of calculation. They are less about profound mathematical insight and more about pattern recognition, like spotting a typo in a poorly written essay.

Divisibility by 2

A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8). This is because any integer can be written as $10k + d$, where $d$ is the last digit. Since $10k$ is always divisible by 2, the divisibility of the entire number hinges on whether the last digit $d$ is divisible by 2. Simple. Elegant. Annoyingly obvious.

Divisibility by 3

A number is divisible by 3 if the sum of its digits is divisible by 3. For example, the number 123 has digits 1, 2, and 3. Their sum is $1+2+3=6$. Since 6 is divisible by 3, 123 is also divisible by 3 ($123 = 3 \times 41$). This works because any power of 10 leaves a remainder of 1 when divided by 3 (e.g., $10 = 3 \times 3 + 1$, $100 = 3 \times 33 + 1$). So, a number like $abc$ (where $a, b, c$ are digits) can be written as $100a + 10b + c$. Modulo 3, this is equivalent to $(1)a + (1)b + c = a+b+c$. If the sum of the digits is divisible by 3, the number itself is. It’s a bit like knowing that if all the ingredients are individually healthy, the resulting dish is probably good for you, assuming you didn’t add a gallon of lard.

Divisibility by 4

A number is divisible by 4 if the number formed by its last two digits is divisible by 4. Consider a number $N$. We can write it as $100k + l$, where $l$ represents the last two digits. Since $100k$ is always divisible by 4 (as $100 = 4 \times 25$), the divisibility of $N$ by 4 depends solely on whether $l$ is divisible by 4. This is a more specific version of the rule for 2, recognizing that $100$ is a multiple of $4$.

Divisibility by 5

A number is divisible by 5 if its last digit is either 0 or 5. Similar to the rule for 2, any number $10k + d$ is divisible by 5 if $d$ is divisible by 5. The only digits divisible by 5 are 0 and 5. This is one of the most straightforward rules, probably why Pythagoras didn’t bother with it.

Divisibility by 6

A number is divisible by 6 if it is divisible by both 2 and 3. Since 2 and 3 are coprime (their greatest common divisor is 1), any number divisible by both must be divisible by their product, 6. This is a consequence of the Chinese Remainder Theorem in a very simplified form.

Divisibility by 7

The rule for 7 is a bit more convoluted, and frankly, if you’re resorting to this, you might as well just do the division. One common method involves taking the last digit of the number, doubling it, and subtracting it from the rest of the number. If the result is divisible by 7, so is the original number. For example, to check 343: double the last digit (3) to get 6. Subtract 6 from the remaining digits (34) to get $34 - 6 = 28$. Since 28 is divisible by 7 ($28 = 7 \times 4$), 343 is also divisible by 7 ($343 = 7 \times 49$). It’s a recursive process. This rule stems from the fact that $10x + y$ is divisible by 7 if and only if $x - 2y$ is divisible by 7. This is because $10(x-2y) = 10x - 20y$, and $10x+y$ differs from $10(x-2y)$ by $21y$, which is always divisible by 7.

Divisibility by 8

A number is divisible by 8 if the number formed by its last three digits is divisible by 8. This is because $1000 = 8 \times 125$. So, any number $1000k + l$ (where $l$ are the last three digits) is divisible by 8 if $l$ is.

Divisibility by 9

Similar to the rule for 3, a number is divisible by 9 if the sum of its digits is divisible by 9. This is because any power of 10 leaves a remainder of 1 when divided by 9 (e.g., $10 = 9 \times 1 + 1$, $100 = 9 \times 11 + 1$). So, $100a + 10b + c \equiv a+b+c \pmod{9}$.

Divisibility by 10

A number is divisible by 10 if its last digit is 0. This is because $10k$ is always divisible by 10.

Importance and Applications

While divisibility might seem like a purely academic exercise, it underpins much of mathematics and has practical applications that are far from trivial.

• Prime Factorization : The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented as a product of prime numbers . Understanding divisibility is the first step in finding these prime factors. This is crucial in cryptography, particularly in algorithms like RSA , which rely on the difficulty of factoring large numbers into their prime components.
• Modular Arithmetic : As mentioned, divisibility rules for sums and differences are foundational to modular arithmetic. This field is essential in computer science (hashing, error correction codes), cryptography, and even in scheduling and cyclical processes.
• Greatest Common Divisor (GCD) and Least Common Multiple (LCM) : Concepts like GCD and LCM are direct applications of divisibility. The GCD of two numbers is the largest number that divides both of them, and the LCM is the smallest number that is a multiple of both. These are used in simplifying fractions, solving linear Diophantine equations, and in various algorithms. For instance, the Euclidean Algorithm for finding the GCD is a classic example of leveraging the properties of divisibility.
• Number Theory Research : Divisibility is a cornerstone of modern number theory. Topics like Mersenne primes , perfect numbers , and the distribution of prime numbers are all deeply intertwined with the concept of divisibility. Even seemingly abstract concepts often trace back to these fundamental relationships.

So, while the rules themselves might be as exciting as watching paint dry, the implications of divisibility ripple through mathematics and technology in ways that are anything but dull. It’s the quiet, unassuming architect of many complex structures.