## Divisibility of integers

An integer m divides an integer n, and we write m | n, when there exists an integer k so n = km.

If m | n, then we say that m is a divisor or a factor of n, and that n is a multiple of m or than n is divisible by m.

3 | 6 since 6 = 3 * 2. That is, there exists an integer k such that 6 = 3k.

For all integers a, a | 0 since 0 = 0 * a. This is true for a = 0 as well.

## Transivity of Divisibility

Let a, b, and c be integers. If a | b and b | c, then a | c.

Proof:
Assume a | b and b | c.
Since a | b there exists an integer r so that ra = b.
Since b | c there exists an integer s so that sb = c.
Substituting ra for b in the previous equation, we get (sr)a = c.
Since sr is an integer, a |c.

##Divisibility of Integer Combinations (DIC)

Let a, b, and c be integers. If a | b and a | c, then for any integers x and y, a | (bx + cy)

Since we are proving an implication, not using it we assume the hypothesis is true to demonstrate the conclusion is true. This is called a Direct Proof.

Proof:
Assume a | b and a | c.
Since a | b there exists an integer m so that ma = b
Since a | c there exists an integer j so that ja = c
Let x and y be integers.
bx + cy = (ma)x + (ja)y = a (mx +jy)
Since mx + jy is an integer, it follows the definition of divisibility that a | (bx + cy)

##Proof of Bounds by Divisibility

###Bounds by Divisibility (BBD)

Let a and b be integers, If a | b and b \(\ne\) 0, then |a| \(\le\) |b|.

Proof:
Since a | b, there exists an integer k so that b = ka.
Since b \(\ne\) 0, k \(\ne\) 0 But if k \(\ne\) 0, |k| \(\ge\) 1
Hence |b| = |ka| = |k||a| \(\ge\) |a|
(You can multiply |k| \(\ge\) 1 by |a| to get |k||a| \(\ge\) |a|)

Divisibility | Home