HOME Mathematics Computer Science
Divisibility Properties
Prerequisites
Show All
Hide All
Divisibility
Show/Hide
﻿
Introduction
• Divisibility is a property of a pair of numbers.
• Given two numbers: d and n, we can say d divides n if there is a third number k in which dk = n
• This property also goes by other names:
• n is a multiple of d
• d is a factor or divisor of n
• n is the dividend
• if d divides n then we write it as:

LaTeX: d \mid n
• if d does not divide n then we write it as:

LaTeX: d \nmid n
Example
• Given the two numbers: 7 and 42, we can say that 7 divides 42 because there is third number: 6 which forms the equality 6 * 7 = 42
• This can be written as:
Code
def is_divisible(divisor, dividend):
return dividend % divisor == 0

print(is_divisible(7, 42))  # prints True

print(is_divisible(4, 42))  # prints False


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)
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