Divisibility


Def For integers a and b with b ≠ 0, we say that b divides a, written b|a if and only if a = b * c for some integer c.

2|10 because 10 = 2 * 5 and 5 ∈ ℤ.
4∤22 because 22 != 4 * c for any integer c there is no integer c such that 22 = 4c.

Properties of Divisibility

  • Transative For integers a, b, c, if a|b and b|c, then a|c.

    Proof: Let a, b, c, be integers.
    Assume a|b and b|c.
    So b = a * c for some integer x and
    c = b * y for some integer y.
    Thus c = a * x * y = a(xy). Since x and y are integers
    we know xy is an integer.
    Thus a|c.

Divisibility Test

6|n <=> 2|n and 3|n
ab|c <= a|c and b|c
Notice: The use of the Walker Property in this example. Result: For integers a, b, c, if
a|c and b|c, then ab|c.
Proof: Let a, b, c be integers.
Assume a|b anf b|c.
Then c = ax and c = by for some integers x and y.
At this point we see that there was a problem in prooving this.
Counterexample: a = 2 b = 4 c = 12
2|12 and 4|14
2 * 4 = 8 and 8∤12.

Result: (Anti-Walker Property)
For integers a, b, c, if ab|c, then a|c and b|c.
Proof: Let a, b, c, be integers.
Assume ab|c. Then c = ab*x for some integer x.
Thus c = a(bx) and we know bx ∈ ℤ. So a|c.
Also c = b * (ax) and we know ax ∈ ℤ.
Thus b|c.

  • True or False (proove or disproove)
    1. If a b and a c, then a bc.
    2. If a bc, then a b and a c.
    3. If a bc, then a b or a c.
    4. If a b and b d, then ac bd.
    5. If a b and c d, then a+c b+d.