## Analysis of a Proof:

## 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|)