MathGoldMedalist
Sign InRegister
Back to Toolkit

Toolkit 46

Divisibility: Definition and Properties

Definition

a∣ba\mid b ("a divides b") if and only if there exists an integer kk such that

b=ak,k∈Z.b=ak,\qquad k\in\mathbb Z.

Like even numbers, which have the form 2k2k.

Properties

1.a∣a1.\quad a\mid a
2.a∣02.\quad a\mid 0
3.±1∣a3.\quad \pm1\mid a
4.a∣b⟹−a∣b,  a∣−b,  −a∣−b4.\quad a\mid b \Longrightarrow -a\mid b,\; a\mid-b,\; -a\mid-b
5.a∣b,  b≠0⟹∣a∣≤∣b∣5.\quad a\mid b,\; b\ne0 \Longrightarrow |a|\le|b|
6.a∣b⟹ac∣bc6.\quad a\mid b \Longrightarrow ac\mid bc
7.a∣b⟹a∣bc7.\quad a\mid b \Longrightarrow a\mid bc
8.a∣1⟹a=±18.\quad a\mid 1 \Longrightarrow a=\pm1
9.a∣b,  b∣c⟹a∣c9.\quad a\mid b,\; b\mid c \Longrightarrow a\mid c
10.a∣b,  a∣c⟹a∣b±c,  a∣bc10.\quad a\mid b,\; a\mid c \Longrightarrow a\mid b\pm c,\; a\mid bc
11.a∣b,  c∣d⟹ac∣bd11.\quad a\mid b,\; c\mid d \Longrightarrow ac\mid bd
12.a∣b⟹an∣bn,n∈Z+12.\quad a\mid b \Longrightarrow a^n\mid b^n,\qquad n\in\mathbb Z^+
13.a∣b,  a∣c⟹a∣mb+nc13.\quad a\mid b,\; a\mid c \Longrightarrow a\mid mb+nc
14.ac∣bc,  c≠0⟹a∣b14.\quad ac\mid bc,\; c\ne0 \Longrightarrow a\mid b
15.a∣b,  b∣a⟹∣a∣=∣b∣15.\quad a\mid b,\; b\mid a \Longrightarrow |a|=|b|
16.a∣b,  a∣c  ⟺  a∣gcd⁡(b,c)16.\quad a\mid b,\; a\mid c \iff a\mid\gcd(b,c)
17.a∣b,  c∣b  ⟺  lcm⁡(a,c)∣b17.\quad a\mid b,\; c\mid b \iff \operatorname{lcm}(a,c)\mid b
18.Euclid’s Lemma:a∣bc,gcd⁡(a,b)=1⟹a∣c18.\quad \text{Euclid's Lemma:}\qquad a\mid bc,\qquad \gcd(a,b)=1 \Longrightarrow a\mid c
19.p∣ab⟹p∣a or p∣b,p prime.19.\quad p\mid ab \Longrightarrow p\mid a \text{ or } p\mid b,\qquad p\text{ prime.}

Proof

1.

a∣aa\mid a

Proof.

a=a⋅1a=a\cdot1

By the definition of divisibility,

a∣a.a\mid a.

2.

a∣0a\mid0

Proof.

0=a⋅00=a\cdot0

Therefore,

a∣0.a\mid0.

3.

±1∣a\pm1\mid a

Proof.

a=1⋅aa=1\cdot a

so

1∣a.1\mid a.

Also,

a=(−1)(−a),a=(-1)(-a),

so

−1∣a.-1\mid a.

4.

a∣b⟹−a∣b,  a∣−b,  −a∣−ba\mid b \Longrightarrow -a\mid b,\; a\mid-b,\; -a\mid-b

Proof.

If

a∣b,a\mid b,

then

b=ak.b=ak.

Hence,

b=(−a)(−k),b=(-a)(-k),

so

−a∣b.-a\mid b.

Also,

−b=a(−k),-b=a(-k),

so

a∣−b.a\mid-b.

Finally,

−b=(−a)k,-b=(-a)k,

so

−a∣−b.-a\mid-b.

5.

a∣b,  b≠0⟹∣a∣≤∣b∣a\mid b,\; b\ne0 \Longrightarrow |a|\le|b|

Proof.

If

a∣b,a\mid b,

then

b=ak.b=ak.

Therefore,

∣b∣=∣a∣∣k∣.|b|=|a||k|.

Since

b≠0,b\ne0,

we have

k≠0,k\ne0,

so

∣k∣≥1.|k|\ge1.

Hence,

∣b∣=∣a∣∣k∣≥∣a∣.|b|=|a||k|\ge|a|.

6.

a∣b⟹ac∣bca\mid b \Longrightarrow ac\mid bc

Proof.

If

a∣b,a\mid b,

then

b=ak.b=ak.

Multiplying both sides by cc,

bc=ack.bc=ack.

Therefore,

ac∣bc.ac\mid bc.

7.

a∣b⟹a∣bca\mid b \Longrightarrow a\mid bc

Proof.

If

a∣b,a\mid b,

then

b=ak.b=ak.

Hence,

bc=ack=a(kc),bc=ack=a(kc),

so

a∣bc.a\mid bc.

8.

a∣1⟹a=±1a\mid1 \Longrightarrow a=\pm1

Proof.

If

a∣1,a\mid1,

then

1=ak.1=ak.

The only integer solutions are

(a,k)=(1,1)(a,k)=(1,1)

or

(a,k)=(−1,−1).(a,k)=(-1,-1).

Therefore,

a=±1.a=\pm1.

9.

a∣b,  b∣c⟹a∣ca\mid b,\; b\mid c \Longrightarrow a\mid c

Proof.

If

a∣b,a\mid b,

then

b=ak1.b=ak_1.

If

b∣c,b\mid c,

then

c=bk2=(ak1)k2=a(k1k2).c=bk_2=(ak_1)k_2=a(k_1k_2).

Therefore,

a∣c.a\mid c.

10.

a∣b,  a∣c⟹a∣b±c,  a∣bca\mid b,\; a\mid c \Longrightarrow a\mid b\pm c,\; a\mid bc

Proof.

If

a∣b,a\mid b,

then

b=ak1.b=ak_1.

If

a∣c,a\mid c,

then

c=ak2.c=ak_2.

Hence,

b±c=a(k1±k2),b\pm c=a(k_1\pm k_2),

so

a∣b±c.a\mid b\pm c.

Also,

bc=(ak1)(ak2)=a(ak1k2),bc=(ak_1)(ak_2)=a(ak_1k_2),

therefore

a∣bc.a\mid bc.

11.

a∣b,  c∣d⟹ac∣bda\mid b,\; c\mid d \Longrightarrow ac\mid bd

Proof.

If

a∣b,a\mid b,

then

b=ak1.b=ak_1.

If

c∣d,c\mid d,

then

d=ck2.d=ck_2.

Therefore,

bd=(ak1)(ck2)=ac(k1k2),bd=(ak_1)(ck_2)=ac(k_1k_2),

so

ac∣bd.ac\mid bd.

12.

a∣b⟹an∣bna\mid b \Longrightarrow a^n\mid b^n

Proof.

By Property 11,

a∣ba\mid b

implies

a2∣b2.a^2\mid b^2.

Repeating the same argument nn times gives

an∣bn.a^n\mid b^n.

13.

a∣b,  a∣c⟹a∣(mb+nc)a\mid b,\; a\mid c \Longrightarrow a\mid (mb+nc)

Proof.

By Property 7,

a∣b⟹a∣mb,a\mid b \Longrightarrow a\mid mb,

and

a∣c⟹a∣nc.a\mid c \Longrightarrow a\mid nc.

Then, by Property 10,

a∣(mb+nc).a\mid (mb+nc).

14.

ac∣bc,  c≠0⟹a∣bac\mid bc,\; c\ne0 \Longrightarrow a\mid b

Proof.

If

ac∣bc,ac\mid bc,

then

bc=ack.bc=ack.

Since

c≠0,c\ne0,

we may divide both sides by cc to obtain

b=ak.b=ak.

Therefore,

a∣b.a\mid b.

15.

a∣b,  b∣a⟹∣a∣=∣b∣a\mid b,\; b\mid a \Longrightarrow |a|=|b|

Proof.

If

a∣b,a\mid b,

then

b=ak1.b=ak_1.

If

b∣a,b\mid a,

then

a=bk2.a=bk_2.

Substituting,

b=(bk2)k1,b=(bk_2)k_1,

so

1=k1k2.1=k_1k_2.

Hence,

k1,k2=±1,k_1,k_2=\pm1,

which implies

b=±a.b=\pm a.

Therefore,

∣a∣=∣b∣.|a|=|b|.

16.

a∣b,  a∣c⟺a∣gcd⁡(b,c)a\mid b,\; a\mid c \Longleftrightarrow a\mid\gcd(b,c)

Proof.

(⇒\Rightarrow)

If

a∣banda∣c,a\mid b \quad\text{and}\quad a\mid c,

then aa is a common divisor of bb and cc.

By the defining property of the greatest common divisor, every common divisor of bb and cc divides

gcd⁡(b,c).\gcd(b,c).

Hence,

a∣gcd⁡(b,c).a\mid\gcd(b,c).

(⇐\Leftarrow)

If

a∣gcd⁡(b,c),a\mid\gcd(b,c),

then, since

gcd⁡(b,c)∣bandgcd⁡(b,c)∣c,\gcd(b,c)\mid b \quad\text{and}\quad \gcd(b,c)\mid c,

Property 9 gives

a∣banda∣c.a\mid b \quad\text{and}\quad a\mid c.

17.

a∣b,  c∣b⟺lcm⁡(a,c)∣ba\mid b,\; c\mid b \Longleftrightarrow \operatorname{lcm}(a,c)\mid b

Proof.

(⇒\Rightarrow)

If

a∣bandc∣b,a\mid b \quad\text{and}\quad c\mid b,

then bb is a common multiple of aa and cc.

By the defining property of the least common multiple,

lcm⁡(a,c)∣b.\operatorname{lcm}(a,c)\mid b.

(⇐\Leftarrow)

If

lcm⁡(a,c)∣b,\operatorname{lcm}(a,c)\mid b,

then, since

a∣lcm⁡(a,c)andc∣lcm⁡(a,c),a\mid\operatorname{lcm}(a,c) \quad\text{and}\quad c\mid\operatorname{lcm}(a,c),

Property 9 gives

a∣bandc∣b.a\mid b \quad\text{and}\quad c\mid b.

18. Euclid's Lemma

a∣bc,gcd⁡(a,b)=1⟹a∣ca\mid bc,\qquad \gcd(a,b)=1 \Longrightarrow a\mid c

Proof.

Since

gcd⁡(a,b)=1,\gcd(a,b)=1,

Bézout's Theorem gives

ax+by=1.ax+by=1.

Multiplying both sides by cc,

axc+byc=c.axc+byc=c.

Since

a∣bc,a\mid bc,

there exists an integer kk such that

bc=ak.bc=ak.

Hence,

byc=aky=a(ky).byc=aky=a(ky).

Therefore,

c=axc+byc =a(xc+ky),c=axc+byc \ = a(xc+ky),

so

a∣c.a\mid c.

19.

p∣ab⟹p∣a or p∣b,p\mid ab \Longrightarrow p\mid a \text{ or } p\mid b,

where pp is prime.

Proof.

If

p∤a,p\nmid a,

then

gcd⁡(p,a)=1\gcd(p,a)=1

because pp is prime.

Since

p∣ab,p\mid ab,

Property 18 (Euclid's Lemma) implies

p∣b.p\mid b.

Therefore,

p∣aorp∣b.□p\mid a \quad\text{or}\quad p\mid b. \quad\square