Massachusetts Institute of Technology Handout 8 6.042J/18.062J: Mathematics for Computer Science Sept 15, 2000 Professors Nancy Lynch and Shlomi Dolev

Mini-Quiz 1

1. Write your name:

2. 1. Determine whether the following sets of integers are pairwise relatively prime.

a) (14, 15, 21) This set of integers is not pairwise relatively prime, since 7 divides both 14 and 21, and 3 divides both 15 and 21.

b) (12, 17, 31, 37) This set of integers is pairwise relatively prime, because for any two integers in the set, their greatest common divisor is 1.

3. Show that ac ≡ bc (mod m), where a,b,c, and m are integers such that m ≥ 2, does not necessarily imply that a ≡ b (mod m). Proof by counterexample:

There are many possible counterexamples. (The important thing is to choose c, m such that gcd(m,c)>1.) Let m=4 and c=2. Then, if we let a=5 and b=15: ac mod m = (10 mod 4) = 2, and bc mod m = (30 mod 4) = 2.

However, 5 ≢ 15 (mod 4).