Divisibility

Rules

Examples

In Depth

An integer \(a\) divides \(b\) (written \(a\mid b\)) if \(b=ka\) for some integer \(k\). Divisibility is reflexive (\(a\mid a\)), transitive (\(a\mid b\) and \(b\mid c\) implies \(a\mid c\)), and antisymmetric on positive integers. The divisors of \(n\) form a lattice under divisibility.

The division algorithm: for any integers \(a\) and \(b>0\), there exist unique \(q,r\) with \(a=qb+r\) and \(0\leq r

Divisibility rules provide shortcuts: \(2\mid n\) iff the last digit is even; \(3\mid n\) iff the digit sum is divisible by 3; \(9\mid n\) iff the digit sum is divisible by 9; \(11\mid n\) iff the alternating digit sum is divisible by 11. These follow from the fact that \(10\equiv1\pmod9\) and \(10\equiv-1\pmod{11}\).

The number of divisors \(d(n)=\prod(e_i+1)\) where \(n=\prod p_i^{e_i}\). The average value of \(d(n)\) is \(\ln n\): \(\frac{1}{N}\sum_{n=1}^N d(n)\sim\ln N\). The maximum of \(d(n)\) for \(n\leq N\) grows like \(N^{c/\ln\ln N}\) for a constant \(c\).

In abstract algebra, divisibility generalizes to any integral domain. An element \(a\) divides \(b\) if \(b=ac\) for some \(c\). Unique factorization domains (UFDs) are rings where every element factors uniquely into irreducibles — the algebraic abstraction of the Fundamental Theorem of Arithmetic.

Key Properties & Applications

The Fundamental Theorem of Arithmetic: every integer \(n>1\) factors uniquely as \(n=p_1^{a_1}\cdots p_k^{a_k}\) (up to order). This is equivalent to \(\mathbb{Z}\) being a unique factorization domain (UFD). The proof uses Euclid's lemma: if \(p\mid ab\) and \(p\) is prime, then \(p\mid a\) or \(p\mid b\).

Divisibility in polynomial rings: \(f(x)\mid g(x)\) in \(F[x]\) (\(F\) a field) iff \(g(x)=f(x)q(x)\) for some polynomial \(q\). The Euclidean algorithm works in \(F[x]\), making it a Euclidean domain and hence a PID and UFD. The GCD of polynomials is computed by the polynomial Euclidean algorithm.

Divisibility tests for large numbers use modular arithmetic. To test if \(n\) is divisible by 7: double the last digit, subtract from the rest, repeat. This works because \(10\equiv3\pmod7\) and \(10^6\equiv1\pmod7\), giving a period-6 pattern.

Further Reading & Context

The study of divisibility connects to many areas of mathematics and its applications. Understanding the foundational definitions and theorems provides the basis for advanced work in analysis, algebra, and applied mathematics.

Historical development: most mathematical concepts evolved over centuries, with contributions from mathematicians across many cultures. The modern axiomatic treatment provides rigor, while computational tools enable practical application.

In modern mathematics, this topic appears in graduate courses and research across pure and applied mathematics. Connections to computer science, physics, and engineering make it a versatile and important area of study. Mastery of the core results and techniques opens doors to research in number theory, analysis, geometry, and beyond.

Recommended next steps: work through the standard theorems with full proofs, explore the connections to related topics listed above, and practice with a variety of problems ranging from computational exercises to theoretical proofs. The interplay between different areas of mathematics is one of the subject's greatest rewards.

Deep Dive: Divisibility

This lesson extends core ideas for divisibility with rigorous reasoning, edge-case checks, and application framing in number theory.

Practice Set

References & Editorial Notes

• Stewart, Calculus.
• Strang, Introduction to Linear Algebra.
• Apostol, Mathematical Analysis.

Last editorial review: 2026-04-14.