Divisibility in Discrete Mathematics

---

---

Divisibility is one of the most basic concepts in mathematics. It helps us find out whether a number can "fit into" another without leaving a remainder. When we work with multiples and factors, divisibility helps us understand how numbers interact. In discrete mathematics, where we work with discrete numbers or integer and finite sets, the concept of divisibility is used in a major portion.

In this article we will see what it means for a number to be divisible, understand some rules, and check a couple of examples for a better understanding.

The Basics of Divisibility

Divisibility means one number can be divided by another without leaving any leftover elements. The leftover part is known as remainder. For example, if we say "6 divides 18," we mean that 18 can be divided by 6 without any remainder. So we could also write this as 6 | 18 which is mathematical shorthand for saying "6 divides 18."

When two numbers, say a and b, they are involved in a division where a divides b. We can say a as a "divisor" or "factor" of b. This is like b is a "multiple" of a. This relationship is basic because it leads us to concepts like factors, multiples, and primes.

For example −

• 4 divide 20 − Yes, because 20 ÷ 4 = 5, a whole number.
• 5 divide 30 − Yes, since 30 ÷ 5 = 6, which also again results in a whole number.
• 7 divide 45 − No, because 45 ÷ 7 = 6 with a remainder of 3. So, we say 7 does not divide 45.

Divisibility Notation and Symbols

In mathematics, when we try to express "4 is a divisor of 20," we simply write 4 | 20. This vertical bar symbol "|" stands for "divides." But, if 4 does not divide 20 evenly, we write it as 4 ∤ 20, where "∤" means "does not divide."

The expression a | b tells us that dividing b by a. It gets the result a whole number. It is like an all-or-nothing concept; either a divides b, or it does not.

Forexample −

• 4 | 28 is true because 28 divided by 4 gives 7, a whole number.
• 5 ∤ 26 is also true because 26 divided by 5 does not yield a whole number.

This divisibility notation makes it easier to work through proofs and examples in discrete math.

Basic Divisibility Rules

Divisibility rules are like shortcuts which helps to find out if one number divides another without going through the division process. There we can follow a few common divisibility rules:

• Divisibility by 2 − A number is divisible by 2 if its last digit is even (0, 2, 4, 6, or 8). Like 36 is divisible by 2 (last digit is 6). But 17 is not divisible by 2 (last digit is 7).
• Divisibility by 3 − A number is divisible by 3 if the sum of its digits is divisible by 3. Like 123 is divisible by 3 (1 + 2 + 3 = 6, which is divisible by 3). But 122 is not (1 + 2 + 2 = 5, not divisible by 3).
• Divisibility by 5 − A number is divisible by 5 if it ends in 0 or 5. For example, 45 is divisible by 5. But 42 is not divisible by 5.

These rules provide quick checks, and these are quite useful when we are working with large numbers or when we need to factor numbers into prime factors.

Divisibility and Integer Operations

When we talk about operations like addition and multiplication within the context of divisibility it becomes interesting. For instance, the sum or difference of two multiples of a number is also a multiple of that number. This property is useful in problem-solving and proofs in discrete math. Let us see some of them.

Sum and Difference of Multiples

If a | b and a | c, then a divides both b + c and b − c.

Example: Consider 4 | 12 and 4 | 16. If we add these, we get −

$$\mathrm{12 + 16 = 28 \quad \text{and} \quad 4 \mid 28}$$

Similarly, if we subtract them −

$$\mathrm{16 - 12 = 4 \quad \text{and} \quad 4 \mid 4}$$

These properties make it easier to work with groups of numbers and build solutions based on divisible pairs or sets.

Multiplying by an Integer

If a | b, then a also divides any multiple of b. For example −

$$\mathrm{\text{If } 3 \mid 9, \text{ then } 3 \mid (9 \times 2) = 18 \text{ and } 3 \mid (9 \times 3) = 27}$$

Practical Examples and Problem Solving

There are multiple such applications of divisibility theory. For instance, if we are planning seating at a large event, we might need to know if tables can be evenly divided among guests. The divisibility is also has applications in computer science, where data structures and algorithms use these rules to ensure efficient calculations and storage.

Example 1: Checking Simple Divisibility

• Problem − Does 6 divide 54?
• Solution − Yes, because 54 ÷ 6 = 9, which is an integer. So, 6 54

Example 2: Multiple Divisibility

• Problem − Does 12 divide 144?
• Solution − Yes, 144 ÷ 12 = 12, so 12 144

Example 3: Divisibility in Sequences

In sequences, divisibility can help find patterns. For example, in the sequence of multiples of 3 (3, 6, 9, 12, ), every term is divisible by 3. If we take any term, say the 10th term (which is 30), it is divisible by 3. Recognizing this can simplify solving related problems.

Using Divisibility in Equations

The concept of divisibility is useful when solving integer equations. Like we need to know if a solution exists or if a particular set of integers. And that can satisfy an equation. The relationship between divisors and multiples becomes our main tool here.

Example

Suppose we need to find integers x and y such that 4x + 6y = 24. We can simplify this by noting that 4 divides 24, so we can factor out 4 to get x + 3y/2 = 6. Then, based on divisibility rules, we can explore potential values of x and y to satisfy the equation.

Conclusion

In this chapter, we explained the concept of divisibility in discrete mathematics. Starting with the basics and some common rules, we explored how to identify if one number divides another. We also highlighted some divisibility rules that make it easier to handle numbers. Finally, we applied these ideas to solve integer-based equations.