# Divisibility Properties

## Prerequisites

### Divisibility Properties

#### Factors of 0

• Every number is a factor of 0: LaTeX:d \mid 0
• Proof:
1. If dk = n then there must always be a k such that dk = 0
2. We can set k = 0

#### 0 as a factor

• If 0 is a factor of n then n = 0: LaTeX:0 \mid n \implies n = 0
• Proof:
1. If dk = n and d = 0 then 0k = n
2. n must be 0

#### 1 as a factor

• 1 is a factor of every number: LaTeX:1 \mid n
• Proof:
1. If dk = n and d = 1 then 1k = n
2. We can set k = n

#### n as a factor

• n is a factor of n: LaTeX:n \mid n
• Proof:
1. If dk = n and d = n then nk = n
2. We can set k = 1

#### factors of 1

• if d is a factor of 1 then d = 1 or d = -1: LaTeX:d \mid 1 \implies d = 1 \text{ or } d = -1
• Proof:
1. If ab = 1 then either a = 1 and b = 1 or a = -1 and b = -1
2. If dk = 1 then either d = 1 or d = -1

#### Transitivity

• if d is a factor of n and n is a factor of m then d is a factor of m: LaTeX:d \mid n \text{ and } n \mid m \implies d \mid m
• Proof:
1. Set n = dk1 and m = nk2
2. In the second equality we can substitute n for dk1 to get m = dk1k2
3. And set k3 = k1k2 to get m = dk3
4. d is a factor of m

#### Multiplication

• if d is a factor of n then ad is a factor of an LaTeX:d \mid n \implies ad \mid an
• Proof: #### Cancellation

• if ad is a factor of an where a is not equal to 0 then d is a factor of n LaTeX:ad \mid an, a \neq 0 \implies d \mid n
• Proof:
1. We set adk = an
2. And divide both sides by a to get dk = n

#### Linearity

• if d is a factor of n and m then d is a factor of an + bm for all a and b LaTeX:d \mid n \text{ and } d \mid m \implies d \mid an + bm \text{ for all a and b}
• Proof:
1. Lets set n = dk1 and m = dk2
2. Then we can rewrite an + bm as adk1 + bdk2
3. And factorize: d(ak1 + bk2)
4. #### Comparison

• if d is a factor of n and both d and n < 0, then dn LaTeX:d \mid n \text{ and } d \mid m \implies d \mid an + bm \text{ for all a and b}
• Proof:
If dk = n, lets consider different cases for k:
1. k < 0
If k is less than 0 then dk is less than 0, this breaks the rule that n > 0 and can be ignored
2. k = 0
If k is 0 then dk is 0, this breaks the rule that n > 0 and can be ignored
3. k = 1
if k is 1 then d equals n, this fits our definition that dn
4. k > 1
if k is greater than 1 then d < n as dk = n