M417 Homework 1 Spring 2004

Instructions: Be prepared to discuss and present in class on Wed., January 21. Written solutions are due Fri., January 23.

1. #4, p. 23
2. #5, p. 23
3. Let a and b be positive integers. Let g = gcd(a, b), and let a'=a/g and b'=b/g. For each of the following statements, if it is false, give a counterexample; otherwise give a proof.
• (a) gcd(a', b') = 1
• (b) gcd(a', b) = 1
• (c) gcd(a, b) = 1 if and only if there are integers x and y such that ax + by = 1
4. Let a and b be positive integers. Let g = gcd(a, b), m = lcm(a, b), and let a' = a/g and b' = b/g and define a'' and b'' such that m = aa'' = bb''.
• (a) Show that m <= ga'b'. Conclude that gm <= ab.
• (b) Show that ab(a''x + b''y) = m(bx + ay) holds for all integers x and y and that m(bx + ay) = gm holds for some integers x and y. Conclude that ab <= gm.
• (c) Conclude that gm = ab.
5. Using the error correcting ``circle'' code discussed in class, determine the correct message encoded by the following code words: 1010101, 1101011, 1100101, 1100011, 1111111.