CSE 321: Discrete Structures
Assignment #4
April 19, 2000
due: Wednesday, April 26

Reading: Rosen, Sections 3.1-3.3, 4.1-4.2

1.

Section 3.1, exercise 24.

2.

Let a, b and c be integers. Prove that if a does not divide bc, then a does not divide c.

3.

Prove that any prime number bigger than 3 is congruent to 1 or 5 modulo 6.

4.

Section 3.2, exercise 10.

5.

Section 3.2, exercise 12.

6.

Section 3.2, exercise 34.

7.

John and Sara have a party to which they invite n other married couples. As is normal at parties, handshaking took place. Of course, noone shook their own hand or their spouses hand (and not everyone shook everyone else's hand). After all the handshaking was over, John asked all the other people present including his wife Sara ``how many different people's hands did you shake this evening?'' Interestingly, they each gave a different answer. From the information given, deduce how many different people's hands Sara shook that evening. Prove your answer by induction on n. (Hint: try working through the solution for several small values of n before going to the general case.)