Quotient-Remainder Theorem; Proofs Involving Cases

Tom Kelliher, MA 115

Oct. 17, 1997

Announcements

Final: 9:00--11:00am on 12/15/97 in HS 149.

Assignment

Read Section 3.6. Problems due Wed. 10/22: 3.3.31, 3.3.33, 3.3.38, 3.4.20, and 3.4.31.

Quiz

Quotient-Remainder Theorem

For any integer n and any positive integer d, there exist unique integers q and r such that

Examples:

1. n=12, d=5.

2. n=37, d=4.

3. n=-39, d=13.

Div and Mod

1. Div: is the quotient of n divided by d.

2. Mod: is the remainder of n divided by d.

If :

1. What is ?

2. What is ?

3. What C++ operators correspond to div and mod?

Proofs with Cases; Parity

Prove that any two consecutive integers have opposite parity.

1. What's parity?

2. This is an example of the proof by division into cases argument form (Example 1.3.8).

Prove that the square of any odd integer can be written as 8m+1 for some integer m.

1. Try it using only the definition of odd.

2. Show that any integer can be represented modulo 4.

3. Try it using the modulo 4 representation of integers.

Prove that the product of any two consecutive integers is even. Two forks in the path:

1. Prove using the fact that any two consecutive integers have opposite parity.

2. Prove by representing integers modulo 2.