HMC Math 55: Discrete Mathematics (Fall, 1998)
Homework

### Assignment #9 (due Wed. 11/11):

Section 29 (pg 212): 11, 12
Section 36 (pg 261): 1, 2, 3 (Note: Should read "(mod 589)")

### Assignment #8 (due Wed. 11/4):

Section 30 (pg 223): 10
Section 31 (pg 230): 1, 2, 3, 6
Section 32 (pg 237): 1, 5

Extra Credit: The idea of an "equivalence relation" was mentioned briefly in class several weeks ago. The definition of a "partition" will be covered in class Friday. The former is covered in Section 12 of the text, while the later is covered in Section 13. There is a natural correspondence between the partitions and the equivalence relations on a set. This fact is also well-covered in the text.

Prove that any equivalence relation on a set induces a partition of that set, and that any partition gives rise to an equivalence relation. Partial (extra) credit will be given for demostrating an understanding of these concepts, even if no rigorous proof is given.
(This proof more or less appears in the book. Simply copying this proof is obviously not acceptable. Write it up yourself.)

### Assignment #7 (due Wed. 10/28):

Section 27 (pg 189): 4ab, 13abde
Section 30 (pg 223): 2, 5, 7, 8

### Assignment #6 (due Fri. 10/23):

Section 26 (pg 178): 15
Section 27 (pg 189): 2, 3, 10, 12
Section 29 (pg 212): 15
6A: Using prime factorizations, prove the following:
(i) If a |bc and gcd(a, b) = 1, then a |c.
(ii) If gcd(a, b) = 1, then gcd(a^2, b^2) = 1. (a^2 means "a squared")
6B: Prove that log10 2 is irrational.
6C: How many zeroes are at the end of 1001! ?

### Assignment #5 (due Wed. 10/14):

Section 25 (pg 178): 4
Section 26 (pg 189): 9, 14, 16 (For #16, the big bowl may be used during the process)
Section 29 (pg 212): 9
5A: Rigorously prove parts (ii) and (iv) of Theorem 1.1, namely that
(ii) If a |b and b |c, then a |c
(iv) If a,b>0 and a |b, then a<=b.
5B: Use Euclid's Algorithm to find...
(i) gcd(812, 238)
(ii) Integers x, y where 812x + 238y = gcd(812, 238)
(iii) Integers x, y where 51x + 20y = 15

### Assignments #1-4

Return to: Math 55 Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu