CSE 321 Winter 2010
Homework #5

Due Friday, February 12th at the start of lecture.  Bring to class to
turn in.

1 [25 points]. How many zeros are there at the end of 100!. Determine this without
computing 100!.

2 [15 points]. Prove or disprove.  If a, b, c are positive integers and a | bc
then either a | b or a | c.

3 [5 points]. Rosen, Chapter 3.6, Problem 2 (a) and (b)

4 [5 points]. Rosen, Chapter 3.6, Problem 4 (a) and (b)

5 [5 points]. Rosen, Chapter 3.7, Problem 36, from (a) to (e).

6 [40 points]. Use strong induction to prove that, for any positive integers a, b:
GCD(2^a-1, 2^b-1) = 2^GCD(a,b) - 1

7 [5 points]. Use the previous problem to compute GCD(2^91-1, 2^133-1)