Divisibility

Context: FIT1058_MOC · multiples and divisors of integers · the relation $d\mid n$ · the foundation of primes, gcd and congruence

Quick Revision

• 🎯 Objective: $d\mid n$: $n=qd$ for some integer $q$ ➔ the relation underpinning all number theory.
• 📦 Core Components: multiple/divisor ➔ $d\mathbb{Z}$ ➔ sum/difference/combination rule.
• ⚡ Key Constraint: $d\mid m,n\Rightarrow d\mid (xm+yn)$, but the converse fails.

📝 Core

1. The Relation (Multiples & Divisors)

• Definition ➔ $d\mid n\iff n=qd$ for some $q\in \mathbb{Z}$ ($d$ a divisor, $n$ a multiple).
• Multiple set ➔ $d\mathbb{Z}=\{\dots ,-2d,-d,0,d,2d,\dots \}$ (evens $=2\mathbb{Z}$).
• Even ➔ ”$n$ even” $\iff 2\mid n$.

2. Combination Rule

• Sum/difference ➔ $d\mid m\wedge d\mid n\Rightarrow d\mid (m\pm n)$.
• General ➔ $d\mid (xm+yn)$ for all $x,y\in \mathbb{Z}$ (Integer Linear Combination).
• Converse fails ➔ $2\mid (3+5)$ but $2\nmid 3,2\nmid 5$.

Key identities:

$d\mid m\wedge d\mid n\Rightarrow d\mid (xm+yn)\forall x,y\in \mathbb{Z}$ $\text{proof: }m=q_{1}d,n=q_{2}d\Rightarrow xm+yn=(x{q}_1+y{q}_2)d$

When It Flips: the sum/difference rule is the engine of the Euclidean Algorithm ($\gcd (a,b)=\gcd (b,a-b)$) and Bézout's identity. $d\mathbb{Z}$ is symmetric about $0$ and always contains $0$ ($q=0$).

📊 Exam Execution Trace

Manual Execution Trace

Divisors of 18:

Step / State	Factorisation	Divisors
0 (Init)	—	—
1	$1\cdot 18$	$1,18$
2	$2\cdot 9$	$2,9$
3	$3\cdot 6$	$3,6$

⚠️ Common Mistakes

• 💡 Converse fails ➔ $d\mid (m+n)$ does not give $d\mid m$ and $d\mid n$; the rule moves from divisors to combinations, never back.

🧠 Active Recall

If $d\mid m$ and $d\mid n$, what else must $d$ divide — and why doesn't $2\mid (3+5)$ make 2 divide 3?

• Hint: Combinations, not summands.

Answer

• Short answer: $d\mid (xm+yn)$ for all integers $x,y$; the converse fails.
• Why: Factor out $d$ ➔ $xm+yn=(x{q}_1+y{q}_2)d$; divisibility of a sum says nothing about summands.

State $d\mid n$ via multiples, remainders, and the set $d\mathbb{Z}$.

• Hint: Three equivalent forms.

Answer

• Short answer: $n=qd$ ⟺ $n\in d\mathbb{Z}$ ⟺ $n\mathrm{mod}d=0$.
• Why: Exact division ➔ all three say ”$d$ goes into $n$ exactly”; $d>0$, $n$ any integer.