Toolkit 46: Divisibility — MathGoldMedalist

Definition

$a\mid b$ (" $a$ divides $b$ ") if and only if there exists an integer $k$ such that

b=ak \qquad k\in\mathbb Z

Like even numbers, which have the form $2k$ .

Properties

\begin{aligned} 1.\quad & a\mid a\\[10pt] 2.\quad & a\mid 0\\[10pt] 3.\quad & \pm1\mid a\\[10pt] 4.\quad & a\mid b\Rightarrow -a\mid b,\ a\mid -b,\ -a\mid -b\\[10pt] 5.\quad & a\mid b,\ b\ne0\Rightarrow |a|\le |b|\\[10pt] 6.\quad & a\mid b\Rightarrow ac\mid bc\\[10pt] 7.\quad & a\mid b\Rightarrow a\mid bc\\[10pt] 8.\quad & a\mid1\Rightarrow a=\pm1\\[10pt] 9.\quad & a\mid b,\ b\mid c\Rightarrow a\mid c\\[10pt] 10.\quad & a\mid b,\ a\mid c\Rightarrow a\mid b\pm c,\ a\mid bc\\[10pt] 11.\quad & a\mid b,\ c\mid d\Rightarrow ac\mid bd\\[10pt] 12.\quad & a\mid b\Rightarrow a^n\mid b^n,\qquad n\in\mathbb Z^+\\[10pt] 13.\quad & a\mid b,\ a\mid c\Rightarrow a\mid mb+nc\\[10pt] 14.\quad & ac\mid bc,\ c\ne0\Rightarrow a\mid b\\[10pt] 15.\quad & a\mid b,\ b\mid a\Rightarrow |a|=|b|\\[10pt] 16.\quad & a\mid b,\ a\mid c\Longleftrightarrow a\mid\gcd(b,c)\\[10pt] 17.\quad & a\mid b,\ c\mid b\Longleftrightarrow \operatorname{lcm}(a,c)\mid b\\[10pt] 18.\quad & \text{Euclid's Lemma:}\qquad a\mid bc,\ \gcd(a,b)=1\Rightarrow a\mid c\\[10pt] 19.\quad & p\mid ab\Rightarrow p\mid a\text{ or }p\mid b,\qquad p\text{ prime} \end{aligned}