**Homework for Mathematics of Information Security **

M360: Fall 2004

** HW 2: due Friday 9/3**

READ: Sections 2.2, 3.1, 3.2, Appendix B.1, B.3 (only examples 1-3) and B.4 (only examples 1-6).

BOOK PROBLEMS: Section 2.13, #2,4,5,6. Section 3.11, # 1.

OTHER PROBLEMS:

A. Find integers x and y so that 105x+121y=1.

B. Show it is impossible for 103 = x^2+y^2 if x and y are odd,
(i.e 103 is not the sum of the squares of two odd integers).

For class discussion on Wednesday (do, but don't hand in).

Choose a number m and make a multiplication table mod m.
Write down some observations about this table.

Bonus Problems:

C. Show the square root of 5 is not a fraction.

D. Show that the Euclidean algorithm takes at most 2 log_2(b) steps.

E. Show that 1 is the gcd of any two consequtive terms in the Fibonacci sequence.