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.