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.

- #4, p. 23
- #5, p. 23
- 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

- 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.

- Using the error correcting ``circle'' code discussed in
class, determine the correct message encoded by the following
code words: 1010101, 1101011, 1100101, 1100011, 1111111.