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.

1. 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))² divides c, prove that ab|c.
2. 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.]
3. # 26, p. 24.
4. 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.
5. 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.