Divisibility Properties

Prerequisites

Divisibility Show

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 d ≤ n 
    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 d ≤ n
    4. k > 1
      if k is greater than 1 then d < n as dk = n