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