
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
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.