Chapter 1

Minus times minus is plus. The reason for this we need not discuss.

-W.H. Auden

1.1 Properties of Integers: If x, y, and z are arbitrary integers, then all of the following are true:

\begin{matrix}(a) & x + y = y + x \\ (b) & (x + y) + z = x + (y + z) \\ (c) & xy = yx \\ (d) & x(yz) = (xy)z \\ (e) & x + 0 = x \\ (f) & 1 · x = x \\ (g) & x(y + z) = xy + xz \\ (h) & −1 · x = −x \\ (i) & x · 0 = 0 \end{matrix}

1.2 Mathematical Induction

Strong and weak mathematical induction are two closely related proof techniques. Both are used to prove assertions about all positive integers. One begins either kind of induction argument by proving that the assertion in question is true for the integer 1. In the case of weak induction one proceeds by assuming that the assertion is true for some arbitrary integer, n, and proving that this assumption implies that the assertion is true for n + 1. This establishes the truth of the assertion for all positive integers. The logic is simple. The first step establishes the result for n = 1, the second step shows that if the assertion is true for some integer it is true for the next integer, combining these two establishes the truth of the assertion for n = 2. Combining this conclusion with the second step establishes the truth of the assertion for n = 3. Now, combining this conclusion with the second step …, but you see where we’re going. It’s beautiful, it’s simple, it’s magic. A little like lifting yourself by your own bootstraps–or maybe watching an infinitely long row of dominoes falling. Strong induction differs from weak only slightly. In the second step one assumes that the assertion to be proved is true for all integers less than or equal some arbitrary n and then proves that the truth of the assertion for n + 1 follows. Sometimes this slightly stronger assumption makes the proof easier.

Basis Step  Inductive Step
Weak (PMI): Show S(n_{0}) is true  Show: S(n)  ⇒ S(n + 1)

Strong (PSI): Show S(n_{0}) is true \begin{matrix}Show: S(n_{0}) \\ S(n_{0}+1) \\ . \\ . \\ . \\ S(n) \end{matrix} \} ⇒ S(n + 1)

PMI stands for principle of mathematical induction. PSI stands for principle of strong induction. (This chart copied, more or less, from Introduction to Mathematical Structures, Steven Galovich.)

Example 1.1 The sum of all odd numbers less than a particular integer is a perfect square. In particular,

1+3+⋯+(2n-1)=n^{2}

Proof: By weak induction. Define S(n): 1+3+⋯+(2n-1)=n^{2}.

Basis Step:

S(1) : 1 = 1.

This is true. Therefore, S(1) holds.

Inductive Step: We show that for each positive integer k, S(k) implies S(k+1).

We assume (the induction hypothesis) 1+3+…+(2k −1) = k^{2}. Adding 2(k+1)-1 to each side of the previous equation gives:

1 + 3 + … + (2k − 1) + (2(k + 1) − 1) = k^{2} + 2(k + 1) − 1.

A little bit of algebra gives:

1 + 3 + … + (2k − 1) + (2k + 1) = k^{2} + 2k + 1.

This is S(k+1).

Therefore, by PMI, 1+3+⋯+(2n-1)=n^{2}.

The Hungarian peripatetic mathematician Paul Erdös liked to talk about “The Book.” The Book has no physical existence, but he imagined it to contain all the “best” proofs possible; those that immediately make clear why the statement they are proving is true. When you die, if you’ve been good, the Supreme Fascist (i.e., god) lets you look at The Book.

A proof of this kind exists for the theorem we just proved by induction, and is as follows:

◯  ◯  \begin{aligned}◯ & & △ \\ & & △ \\ △ & △ & △ \end{aligned}  …  \begin{aligned}◯ & & △ & ♣ & ♢ & ♠ \\ & & △ & ♣ & ♢ & ♠ \\ △ & △ & △ & ♣ & ♢ & ♠ \\ ♣ & ♣ & ♣ & ♣ & ♢ & ♠ \\ ♢ & ♢ & ♢ & ♢ & ♢ & ♠ \\ ♠ & ♠ & ♠ & ♠ & ♠ & ♠ \end{aligned}  …

First day, September 9, notes scribed by Marie Hill

Well-Ordering Principle If S is a nonempty set of positive integers, then S has a least element.

This is a useful axiom. Don’t believe it? Check out the next proof!

Theorem 1.1 The Division Algorithm If a and b are integers, such that b > 0, then there exist unique integers q and r such that a = qb + r and 0 ≤ r < b. (Note that a corollary of this will be proved later, dealing with the case b < 0.)

Proof: Define the set S as:

S = {a − xb | x ∈ Z, a − xb > 0}

1. Proof that S is not empty: Since b ≥ 1, if we take x = −a, we get:

a − (−a)b ≥ 0

So,

a − (−a)b + b > 0
a − (−a − 1)b > 0

For example, these are all members of the set, where a = 42 and b = 5:

42 − (−1)5
42 − (0)5
42 − (1)5
42 − (2)5

By the Well-Ordering Principle, S has a least element. We will call it r. There is some integer that will give this r. We will call it q:

a − qb = r

So,

a = qb + r 2. Proof that 0 ≤ r < b:

Let’s try a proof by contradiction. Suppose r ≥ b. Then, after distributing the b we get

a = (q + 1)b + (r − b)

where 0 ≤ r − b < r. So, r − b is in S. This is a contradiction: We assumed that r was the least element in S. Thus, r < b.

3. Proof of Uniqueness: Suppose there exist q, q′ and r, r′ such that a = qb + r, a = q′b + r′, and 0 ≤ r, r′ < b. Then,

qb + r = q′b + r′
b|q − q′| = |r − r′|

Consider |r − r′|, we know that 0 ≤ r < b and −b < −r′ ≤ 0 Adding these together, we see that

−b < r − r′ < b
|r − r′| < b

Therefore,

b|q − q′| = |r − r′| < b

However, we know that b is a positive integer. Therefore, q − q′ = 0. So, q = q′ and r = r′ Thus, q and r are unique.

This tells us that any integer can be written in one of the following forms, where k is an integer: 4k, 4k + 1, 4k + 2, 4k + 3. (Or, for that matter, 67k, 67k + 1, 67k + 2, …, 67k + 66.)

Note that when we square these integers, they can all be written in the form 4L or 4L + 1

(4k)^{2} = 16k^{2} = 4L
(4k + 1)^{2} = 16k^{2} + 8k + 1 = 4L + 1
(4k + 2)^{2} = 16k^{2} + 8k + 4 = 4L
(4k + 3)^{2} = 16k^{2} + 24k + 9 = 4L + 1

Thus, all perfect squares are of the form 4L or 4L + 1. So, for example, it is immediately clear that 13, 546, 987, 631 is not a square. What about 13, 546, 987, 632? Oh well, I didn’t say it would solve all your problems.

Corollary 1.1.1 For any b ≠ 0 where a and b are integers, there exist uniqe integers q and r such that a = qb + r and 0 ≤ r < |b|.

Proof: If b is negative, we simply use |b| and the above result:

a = q|b| + r

Then

a = −qb + r

Note that if b = 0, q is not unique. Thus, the Division Algorithm is not true when b = 0, that is, don’t try to divide by zero. You knew that. Definition We say a divides b, written a | b, if a ≠ 0 and there exists c such that b = ac. Theorem 1.2 For non-zero a,

1. a | 0, 1 | a, and a | a.

2. a | 1 if and only if a = ±1.

3. If a | b and c | d, then ac | bd.

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

5. If a | b and b ≠ 0, then | a |≤| b |.

6. If a | b and b | a, then | a |=| b |.

7. If a | b and b | c, then a | (bx + cy) for any integers x and y. Proof of 1.2.7: Since a | b, ∃r such that ar = b. Since a | c, ∃s such that as = c. So, bx + cy = arx + asy = a(rx + sy). This tells us a | (bx + cy).

Definition We say d is the greatest common divisor of integers a and b, with a ≠ 0 or b ≠ 0, if:

1. d | a and d | b

2. c | a and c | b implies c ≤ d. Helpful hint: Use common sense to decipher phrases such as “locally eventually onto” and “greatest common divisor.” Mathematicians always say exactly what they mean. Usually. Theorem 1.3 Given integers a, b not both zero, there exist integers x, y such that gcd(a, b) = ax + by. Example 1.1 Take a = −12, b = 30, gcd(−12, 30) = 6. Then 6 = −12 × 2 + 30 × 1. Note, x and y are not unique. For example, 6 = −12 × 12 + 30 × 5 as well.

Proof: We will first find a common divisor of a and b, then show that this divisor is indeed the greatest number that divides both a and b. Let S = {au+bv | u, v are integers, au+bv > 0}. S is the set of all positive integers of the form au + bv for fixed a and b. Our first job is to show that S is nonempty. If we let u = a, v = b, we have a^{2} + b^{2}. Since a^{2} + b^{2} must be positive, it is in S. Now that we know we have a nonempty set, we can apply the Well-Ordering Principle, which tells us that S must have a least element. Call this element d. We’ll now show that d =gcd(a, b). Since d ∈ S, d = ax_{0} + by_{0} for some integers x_{0}, y_{0}. By the Division Algorithm, a = qd + r, 0 ≤ r < d for integers q and r. Then

a − qd = r

Substituting for d,

a − q(ax_{0} + by_{0}) = r
a(1 − qx_{0}) − qby_{0} = r

Since we can write r in this form, either r ∈ S or r = 0. (Recall that r cannot be negative). Now, r is strictly less than d, and we chose d to be the minimal element of S, so r ∉ S. Therefore, r = 0 and d | a. A similar argument tells us d | b. Now we know that d is a common divisor of a and b. It remains to be shown that d is their greatest common divisor. To see this, suppose that c is a greater common divisor: c | a and c | b with c > d. But since d = ax_{0} + by_{0}, c | d by 1.2.7. From this fact and 1.2.5, c ≤ d. This contradicts our assumption that c > d.

Corollary 1.3.1 If a, b are integers, a, b not both zero, then T = {ax + by | x, y ∈ Z} is precisely the multiples of gcd(a, b).

Proof: We must show double containment. All multiples of gcd(a, b) ∈ T: From the previous theorem, we can write gcd(a, b) as ax_{0} + by_{0} for some x_{0}, y_{0}. Then any multiple of gcd(a, b) can be written k(ax_{0} + by_{0}) = kax_{0} + kby_{0}, which is in T. All elements of T are multiples of gcd(a, b): Take ax_{0}+by_{0} ∈ T. Let g =gcd(a, b). Then, since g divides both a and b, Theorem 1.2.7 tells us that g divides ax_{0} +by_{0} as well. So ax_{0} +by_{0} is a multiple of gcd(a, b).

Definition Two integers are relatively prime if their greatest common divisor is 1.

Corollary 1.3.2 (Euclid’s lemma) If a | bc and gcd(a, b) = 1, then a | c.

Proof: By the previous theorem, ∃x, y such that

1 = ax + by.
or, c = acx + bcy

Since a | ac and a | bc, we can use Theorem 1.2.7 to say that a | c.

Theorem 1.4 (The Euclidean Algorithm) Given two integers x and y, with x > y, use the following process to find gcd(x, y):

x = q_{1}y + r_{1}
y = q_{2}r_{1} + r_{2}
r_{1} = q_{3}r_{2} + r_{3}
...
r_{k−1} = q_{k+1}r_{k} + r_{k+1}
r_{k} = q_{k+2}r_{k+1} + 0

The process continues until we have a remainder of zero; gcd(x, y) is the last non-zero remainder, r_{k+1}.

Proof: We’ll first show that r_{k+1} is a divisor of x and y, and then show that it is the greatest common divisor. Finally, we’ll show that the algorithm must terminate.

From the last line, r_{k+1} | r_{k}, so r_{k+1} | q_{k+1}r_{k}. Also, r_{k+1} | r_{k+1}. Then from Theorem 1.2.7 and the next-to-last line, r_{k+1} | r_{k−1}. We can then use Theorem 1.2.7 on each preceding line until we’ve shown that r_{k+1} divides each of the remainders, as well as x and y. This shows that r_{k+1} is a common divisor of x and y.

Now suppose that x and y have a greater common divisor, z. If z divides x and y, then, by the first line and Theorem 1.2.7, it must divide r_{1}. Given this, z must also divide q_{2}r_{1}, so the second line and 1.2.7 tell us that that z | r_{2}. Eventually, we will find that z | r_{k+1}. But z > r_{k+1}, which is a contradiction. Therefore, r_{k+1} must be the greatest common divisor of x and y.

We still need to show that we are guaranteed an eventual remainder of zero. This occurs because of the restrictions on r in the division algorithm. The division algorithm states that any integer can be written in the form qb+r, with 0 ≤ r < b. This means that our remainders decrease with each step and are bounded below by zero. They must eventually hit zero.

The Euclidean Algorithm provides us with a tool for expressing the gcd(a, b) as the linear combination guaranteed to exist by Theorem 1.3. We can work backwards and rearrange terms as follows:

r_{k+1} = r_{k−1} − q_{k+1}r_{k}
= r_{k−1} − q_{k+1}[r_{k−2} − q_{k}r_{k−1}]
= r_{k−1}(1 − q_{k}) − q_{k+1}r_{k−2}

Then substitute for r_{k−1}, etc, until what is left is an expression in terms of x and y.

Tantalizing Tidbit: Math and stand-up comedy have a lot in common.

Let’s do a specific example...

Example 1.2 Find gcd(963,657).

963 = 1 × 657 + 306
657 = 2 × 306 + 45
306 = 6 × 45 + 36
45 = 1 × 36 + 9
36 = 4 × 9 + 0

So gcd(963,657) = 9. Example 1.3 Express 9 as a linear combination of 963 and 657.

9 = 45 − 1 × 36
= 45 − (306 − 6 × 45)
= 7 × 45 − 306
= 7(657 − 2 × 306) − 306
= 7 × 657 − 15 × 306
= 7 × 657 − 15(963 − 1 × 657)
9 = 22 × 657 − 15 × 963

Second day, September 11, notes scribed by Krista Caner and Mimi Cukier