M417 Homework 2 Spring 2004

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

- Let a, b and c be positive integers such that
a|c and b|c.
- (a) If gcd(a,b)=1, prove that ab|c.
- (b) Give a counterexample to the statement: If (gcd(a,b))
^{2} divides c, prove that ab|c.

- Prove that there are infinitely many primes. [Hint:
if S is any nonempty finite set of primes, and P is
the product of the primes
in the set S, show that no prime in S divides P+1.]
- # 26, p. 24.
- Let R be the relation on the set of integers defined by
aRb exactly when a - b is odd. Determine with
justification whether or not
R is: reflexive; symmetric; transitive.
- Convert your student ID into a string of 1's and 0's by replacing
each odd digit by 1 and each even digit by 0. Take the rightmost substring
of three consecutive digits which is not either 000 or 111. (For example,
if your ID is 485-73-617, you get 001110111 and then 011.) If you can't avoid
000 or 111 (because your ID consists only of even digits or only of odd digits),
take the string 011. Let 1 represent True, and let 0 represent False.
Now say your string is abc.
Define a relation R on the set of integers such that
reflexivity is a for R (i.e., either True or False, according to
your value of a), symmetry is b and transitivity is c.