1 Basic definition and notation
1.1 Definition of divisibility
Divisibility is the relation that holds when one integer is an exact multiple of another. If an integer \(a\) can be written as \(a=bq\) for some integer \(q\), with \(b\neq 0\), then \(a\) is divisible by \(b\). In this situation, division by \(b\) produces no remainder in the usual integer sense.
This concept is one of the central building blocks of arithmetic. It separates exact division from fractional division and provides a precise way to compare integers through factors and multiples.
1.2 Divisor, factor, and multiple
If \(b\) divides \(a\), then \(b\) is called a divisor or factor of \(a\), and \(a\) is called a multiple of \(b\). These terms describe the same relationship from opposite directions. For example, 3 is a factor of 12, while 12 is a multiple of 3.
The same integer may have many divisors. The number 12, for instance, has divisors 1, 2, 3, 4, 6, and 12, along with their negative counterparts if negative divisors are included.
1.3 Divisibility notation and examples
The standard notation for divisibility is \(b \mid a\), read as “\(b\) divides \(a\).” The notation \(b \nmid a\) means that \(b\) does not divide \(a\). Thus \(4 \mid 20\), but \(4 \nmid 22\).
Examples help clarify the meaning. Since \(18 = 6 \cdot 3\), the statement \(6 \mid 18\) is true. Since there is no integer \(q\) satisfying \(18 = 5q\), the statement \(5 \mid 18\) is false.
1.4 Negative integers and zero
Divisibility is commonly discussed for integers, including negative numbers. If \(b \mid a\), then \((-b) \mid a\) as well, because changing the sign of the divisor only changes the sign of the quotient. Likewise, if \(b \mid a\), then \(b \mid (-a)\).
Zero has special behavior. Every nonzero integer divides 0, since \(0 = b\cdot 0\). However, 0 divides no integer, because division by zero is undefined. Also, 0 is divisible by every nonzero integer.
2 Fundamental properties
2.1 Transitivity and reflexive behavior
Divisibility is transitive: if \(a \mid b\) and \(b \mid c\), then \(a \mid c\). This follows by substituting one integer multiple into another. For example, if 2 divides 6 and 6 divides 18, then 2 divides 18.
Divisibility is also reflexive for nonzero integers, since any integer \(a\neq 0\) divides itself: \(a=a\cdot 1\). This makes divisibility a natural relation for organizing integers by their factor structure.
2.2 Compatibility with addition
If \(a \mid b\) and \(a \mid c\), then \(a \mid (b+c)\). This property reflects the fact that multiples of the same integer remain multiples when added together. It is one of the most useful rules in elementary number theory.
The same idea works for subtraction as well, since \(b-c\) is simply the sum of \(b\) and \(-c\). Thus divisibility is stable under linear combinations with integer coefficients.
2.2.1 Sum and difference rules
If \(a \mid b\) and \(a \mid c\), then \(a\) divides both \(b+c\) and \(b-c\). For example, 4 divides 12 and 20, so it also divides 32 and 8. These rules are often used to prove divisibility indirectly.
Conversely, if \(a\mid b\) and \(a\mid (b+c)\), then \(a\mid c\). Such rearrangements are useful in algebraic manipulations and proofs involving integer equations.
2.3 Compatibility with multiplication
If \(a \mid b\), then \(a \mid bc\) for every integer \(c\). Multiplying a multiple of \(a\) by another integer preserves divisibility by \(a\). For instance, since 5 divides 15, it also divides 15 times any integer.
This property extends to products of divisible numbers. If \(a \mid b\) and \(c \mid d\), then \(ac \mid bd\) provided the factors are arranged appropriately. Such facts are fundamental in factorization arguments.
2.4 Divisibility by products
If \(a \mid b\) and \(a \mid c\), then \(a\) divides any integer combination of \(b\) and \(c\), including products formed with additional integers. More specifically, if \(a \mid b\), then \(a \mid bc\) regardless of \(c\).
Product rules are especially helpful when analyzing prime factors. They allow divisibility statements about large numbers to be reduced to statements about smaller components.
3 Divisibility tests
3.1 Base-10 divisibility criteria
In base 10, several divisibility rules let one determine quickly whether a number is divisible by a small integer. These tests depend on the decimal form of the number and often use only the last digit or a simple digit sum.
They are practical shortcuts rather than definitions. Each test is a consequence of modular arithmetic and the fact that powers of 10 have specific remainders when divided by small integers.
3.1.1 Tests for 2, 3, 4, 5, 6, 8, 9, and 10
A number is divisible by 2 if its last digit is even. It is divisible by 5 if its last digit is 0 or 5, and by 10 if its last digit is 0.
For 3 and 9, the sum of the digits is decisive: a number is divisible by 3 if its digit sum is divisible by 3, and by 9 if the digit sum is divisible by 9. A number is divisible by 4 if its last two digits form a number divisible by 4, and by 8 if its last three digits form a number divisible by 8.
A number is divisible by 6 exactly when it is divisible by both 2 and 3. These criteria are widely taught because they simplify mental arithmetic and checking calculations.
3.2 Tests for 11 and other bases
A classic test for 11 uses alternating sums of digits. If the difference between the sum of digits in alternating positions is divisible by 11, then the number itself is divisible by 11. This rule arises from the behavior of powers of 10 modulo 11.
Similar tests can be developed for other bases and divisors. In general, a divisibility rule in a given base reflects how place values interact with modular arithmetic.
3.3 Digital sum methods
Digital sum methods repeatedly add the digits of a number until a smaller number is obtained. This process is especially useful for testing divisibility by 3 and 9. For example, 48 has digit sum 12, and 1 + 2 = 3, so 48 is divisible by 3.
These methods are convenient for checks and puzzles, though they do not replace formal proofs. They are based on the fact that a number and the sum of its digits have the same remainder modulo 9, and similarly modulo 3.
4 Prime factorization and divisibility
4.1 Prime numbers and prime divisors
A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. Prime divisors are the prime factors appearing in the factorization of a number. They are the basic building blocks of the integers.
If a prime \(p\) divides a product, then it often divides one of the factors. This property makes primes central to divisibility arguments and to the structure of the integers.
4.2 Fundamental theorem of arithmetic
The fundamental theorem of arithmetic states that every integer greater than 1 can be written uniquely as a product of primes, up to the order of the factors. For example, 60 factors as \(2^2\cdot 3\cdot 5\).
This theorem explains why divisibility can be studied through prime decomposition. Once the prime factors of a number are known, its divisors can be listed systematically.
4.3 Multiplicity of prime factors
The multiplicity of a prime factor is the number of times it appears in the prime factorization. In \(72 = 2^3 \cdot 3^2\), the multiplicity of 2 is 3 and that of 3 is 2. Multiplicity controls many divisibility properties.
Knowing multiplicities helps determine how strongly one number divides another. It also appears in formulas for gcds, lcms, and counts of divisors.
4.4 Divisibility in terms of factor exponents
If \(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\), then a positive integer divides \(n\) exactly when its prime exponents do not exceed those in \(n\). In other words, every prime appearing in the divisor must appear with no larger exponent than it does in \(n\).
This criterion is a direct consequence of unique prime factorization. It gives a complete description of the divisors of a number and is a powerful tool for comparing integers.
5 Greatest common divisor and least common multiple
5.1 Common divisors
A common divisor of two integers is a number that divides both of them. The set of common divisors measures the overlap in their factor structure. For example, the common divisors of 18 and 24 are 1, 2, 3, and 6.
Common divisors play an important role in simplifying fractions, solving equations, and understanding how numbers share factors.
5.2 Greatest common divisor
The greatest common divisor, or gcd, of two integers is the largest positive integer dividing both. It is usually written \(\gcd(a,b)\). For example, \(\gcd(18,24)=6\).
The gcd summarizes the shared divisibility of two numbers. When it equals 1, the numbers are called relatively prime or coprime.
5.2.1 Euclidean algorithm
The Euclidean algorithm is an efficient method for computing the gcd of two integers. It repeatedly replaces a pair of numbers by a smaller pair using remainders, until the remainder becomes zero. The last nonzero remainder is the gcd.
This method is one of the oldest and most effective algorithms in mathematics. Its efficiency makes it useful in both theoretical and computational settings.
5.2.2 Bezout's identity
Bezout's identity states that the gcd of two integers can be expressed as an integer linear combination of them. If \(d=\gcd(a,b)\), then there exist integers \(x\) and \(y\) such that \(ax+by=d\).
This result connects divisibility with linear algebraic structure over the integers. It is especially important in solving Diophantine equations and proving properties of coprime numbers.
5.3 Least common multiple
The least common multiple, or lcm, of two integers is the smallest positive integer divisible by both. It is written \(\operatorname{lcm}(a,b)\). For example, the least common multiple of 6 and 8 is 24.
The lcm captures the first point at which two divisibility patterns overlap. It is useful in fraction arithmetic, periodicity, and combinatorial counting.
5.4 Relationship between gcd and lcm
For positive integers \(a\) and \(b\), the product of the gcd and lcm equals \(ab\): \[ \gcd(a,b)\cdot \operatorname{lcm}(a,b)=ab. \] This identity follows from prime factorization and the way exponents combine.
The formula is often used to compute one quantity from the other. It also highlights the complementary roles of common factors and common multiples.
6 Euclidean division and remainders
6.1 Quotient and remainder theorem
| The quotient and remainder theorem states that for integers \(a\) and nonzero \(b\), there exist unique integers \(q\) and \(r\) such that \(a=bq+r\), where \(0\le r< | b | \). Here \(q\) is the quotient and \(r\) is the remainder. |
|---|
This theorem formalizes ordinary integer division. Divisibility is the special case in which the remainder is zero.
6.2 Division algorithm
The division algorithm is the procedure underlying the quotient and remainder theorem. It expresses every integer as a multiple of another integer plus a remainder smaller in absolute value than the divisor. The algorithm is foundational for computation with integers.
It is used repeatedly in number theory, especially in the Euclidean algorithm and modular arithmetic. Its repeated application generates quotient sequences and remainders that reveal structural information.
6.3 Exact divisibility and remainder zero
A number \(a\) is divisible by \(b\) exactly when dividing \(a\) by \(b\) leaves remainder zero. In the quotient-remainder form \(a=bq+r\), this means \(r=0\). Exact divisibility is therefore the simplest case of integer division.
This viewpoint is often the most practical in calculations. It translates a factor relation into a concrete arithmetic test.
6.4 Congruence modulo n
Congruence modulo \(n\) records when two integers have the same remainder upon division by \(n\). One writes \(a \equiv b \pmod n\) if \(n\mid(a-b)\). This notation extends divisibility into a broader arithmetic framework.
Congruence is closely tied to divisibility because divisibility of differences determines equality of remainders. It is a central language for modular arithmetic and many modern number-theoretic results.
7 Advanced topics
7.1 Divisibility in rings and integral domains
The notion of divisibility extends beyond integers to algebraic structures called rings. In a ring, an element \(a\) divides an element \(b\) if \(b=ac\) for some ring element \(c\). In an integral domain, divisibility behaves more like integer divisibility because there are no zero divisors.
This generalization allows number-theoretic ideas to be applied in algebra and geometry. It also helps compare the factorization behavior of different algebraic systems.
7.2 Units and associates
A unit is an element that has a multiplicative inverse within the ring. Two elements are associates if one differs from the other by multiplication by a unit. In the integers, the associates of a nonzero number are just its positive and negative forms.
Associates have the same divisibility behavior up to multiplication by units. This idea is important when factorization is studied in more general algebraic settings.
7.3 Divisibility in polynomial rings
In polynomial rings, divisibility means that one polynomial can be written as the product of another polynomial and a third polynomial. For example, \(x-1\) divides \(x^2-1\) because \(x^2-1=(x-1)(x+1)\).
Polynomial divisibility mirrors integer divisibility in many ways, but it also has distinct features. It is used in factorization, interpolation, and the study of roots.
7.4 Divisibility sequences
A divisibility sequence is a sequence of integers in which the index relation \(m\mid n\) implies that the \(m\)-th term divides the \(n\)-th term. Familiar examples include sequences such as \(a^n-1\) under suitable conditions.
These sequences connect divisibility with recurrence relations and algebraic formulas. They appear in classical number theory and in the study of integer sequences with strong arithmetic structure.
8 Applications
8.1 Simplifying fractions
Divisibility is used to reduce fractions to lowest terms. If the numerator and denominator share a common divisor greater than 1, both can be divided by that number without changing the value of the fraction. Repeating this process yields a simplified form.
This application relies directly on the gcd. It is one of the most familiar practical uses of divisibility in school arithmetic.
8.2 Solving linear Diophantine equations
Linear Diophantine equations seek integer solutions to equations such as \(ax+by=c\). A solution exists only when the gcd of \(a\) and \(b\) divides \(c\). This criterion is a direct consequence of Bezout’s identity.
Once solvability is established, divisibility methods help construct all solutions. Such equations arise in counting, scheduling, and algebraic problems.
8.3 Modular arithmetic computations
Modular arithmetic depends on divisibility through congruence relations. Calculations are performed using remainders, which reduces large numbers to manageable representatives. This approach is useful for simplifying computations involving powers, products, and sums.
Divisibility rules and residue classes make modular arithmetic efficient and systematic. It is widely used in proofs, algorithms, and combinatorial reasoning.
8.4 Cryptographic and computational uses
Divisibility underlies many computational methods in number theory, especially those involving primes, factorization, and modular arithmetic. These ideas support algorithms for checking exact division, computing gcds, and working with large integers.
In cryptographic systems, divisibility-related structure helps define arithmetic problems that are easy to perform one way but difficult to reverse without special information. More generally, divisibility is a foundational tool in computer algebra and algorithm design.