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.

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.