Let a and b be integers. If a | b and b | a, then a = ± b.

**Can we use Bounds by Divisibility (BBD) if we did not say a \(\ne\) 0 and b \(\ne\) 0**

The answer to that is we must consider a,b = 0 as a special case, and use BBD for other cases.

**Proof:**

**Case 1:**
Since 0 | 0 and 0 \(\nmid\) n for any non-zero integer n,

then when a = 0, b must be zero and vice versa

**Case 2:**

When a \(\ne\) 0, and b \(\ne\) 0

From a | b and b \(\ne\) 0, we can use BBD to get |a| \(\le\) |b|

From b | a and a \(\ne\) 0, we can use BBD to get |b| \(\le\) |a|

Hence |a| = |b|

Therefore a = ± b

A \(\Rightarrow\) B and \(\lnot\)A v B are the same

A | B | A \(\Rightarrow\) B | \(\lnot\)A | not A v B |
---|---|---|---|---|

T | T | T | F | T |

T | F | F | F | F |

F | T | T | T | T |

F | F | T | T | T |

\(\lnot\)(A \(\Rightarrow\) B) \(\equiv\) \(\lnot\)((\(\lnot\)A) v B)

\(\equiv\) ((\(\lnot\)(\(\lnot\)A)) \(\land\) (\(\lnot\) B))

\(\equiv\) A \(\land\) (\(\lnot\) B)

In A then B **Implication**

A and not B **Negated Implication**

If a | b and b|c then a|c.

**Negated Implication:**

a | b and b | c and a \(\nmid\) c

If a | bc then a|b or a|c.

**Negated Implication:**

a | bc and a \(\nmid\) b and a \(\nmid\) c

If a | b and b \(\ne\) 0, then|a|≤|b|.

**Negated Implication:**

a | b and b \(\ne\) 0 and |a| > |b|

“If m is an integer and 14 | m,

prove that 7 | 135m + 693”.

Note that 7 \(\nmid\) 135, so this is not a straight-forward result.

Recall previously: **Proposition (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).

**Proof:**
Assume 14 | m

Since 7 | 14, by Transivity of Divisibility 7 | m

m = 7k, for some integer k

Now 135m + 693 = 135(7k) + 7(99) = 7(135k + 99)

As 135k + 99 is an integer, 7 | (135m + 693)

Given an implication:

If A then B.

the **converse** of “If A then B” (A \(\Rightarrow\) B)
is “If B then A” (B \(\Rightarrow\) A)

An implication and its converse are not logically related.

##Sets

Sets are collection of objects, called **elements** or **members**

∅ = { }. The empty-set has nothing in it.

{∅} has one element, namely the empty set, so

{∅} ≠ ∅.

\(\mathbb{R}\) is the set of real numbers. This is essentially the set that contains every possible number we have seen (unless you have seen complex numbers).

\(\mathbb{Q}\) is the set of rational numbers. These are numbers of the type 2, 1, 5 , 2, etc. The members are fractions, with numerator and denominator both being integers, and denominator cannot be zero.

\(\mathbb{Z}\) = {…,−3,−2,−1,0,1,2,3,…}, the set of integers (whole numbers)

\(\mathbb{N}\) = {1,2,3,…}, the set of natural numbers (positive integers). Note that in MATH 135, N starts at 1 and 0 ∉ N. This may be different that what you learn in CS.