Divisibility
ArithmeticDivisibility is the property of one integer being divided by another with no remainder; divisibility rules provide shortcuts for checking this.
Formula
a \text{ is divisible by } b \text{ if } a = b \times k \text{ for some integer } k
Definition
A number is divisible by another if dividing them leaves no remainder. Divisibility rules give you quick tricks to check this without dividing.
Example
A number is divisible by $2$ if it ends in $0$, $2$, $4$, $6$, or $8$. So $348$ is divisible by $2$. A number is divisible by $5$ if it ends in $0$ or $5$.
Key Insight
Divisibility rules save time: you can tell $312$ is divisible by $3$ just by adding $3+1+2=6$, and since $6$ is divisible by $3$, so is $312$.
Definition
$a$ is divisible by $b$ (written $b \mid a$) if there exists an integer $k$ such that $a = bk$ (remainder $0$). Key divisibility rules: by $2$ (even last digit), by $3$ (digit sum divisible by $3$), by $4$ (last two digits divisible by $4$), by $5$ (ends in $0$ or $5$), by $9$ (digit sum divisible by $9$), by $11$ (alternating digit sum divisible by $11$).
Example
Is $2{,}346$ divisible by $6$? It must be divisible by both $2$ and $3$. Last digit $6$: yes, divisible by $2$. Digit sum $2+3+4+6=15$, divisible by $3$: yes. So $2346$ is divisible by $6$.
Key Insight
Divisibility rules for $3$, $9$, and $11$ derive from the fact that $10 = 9+1$ (so $10^k \equiv 1 \pmod 9$ for all $k$) and $10 = 11-1$ (so $10^k \equiv (-1)^k \pmod{11}$). They are applications of modular arithmetic.
Definition
Divisibility in $\mathbb{Z}$ defines a partial order: $b \mid a$ iff $b\mathbb{Z}$ contains $a\mathbb{Z}$ (as ideals). This order makes $\mathbb{Z}^+$ a distributive lattice under GCD (meet) and LCM (join). In any integral domain, divisibility is a preorder. In a UFD it refines to a lattice via the partial order on prime exponents.
Example
Divisibility test for $7$ (no simple rule): repeatedly apply $2a_0 - b$ where $b$ is the remaining digits and $a_0$ is the last digit, until small. For $343$: $34 - 2(3) = 28$; $28$ is divisible by $7$, so $343$ is too ($343 = 7^3$).
Key Insight
The divisibility relation in $\mathbb{Z}$ is the starting point for the theory of ideals. Dedekind's insight was that in rings of algebraic integers, unique prime ideal factorization restores the divisibility structure lost by the failure of unique element factorization.