Discrete Math Proofs

1. Let a and b be integers with gcd(a; b) = 1. Prove for any integer x, if ajx and bjx then abjx. 2. Let a and b be integers. Prove that gcd(a; b) = 1 if and only if there exists inte- gers x and y such that ax + by = 1. 3. Let p1; p2; : : : ; pn be prime numbers. Prove that none of p1; p2; : : : pn divide p1p2 : : : pn+ 1. 4. Show that there are innitely many prime numbers. (You can use the previous ques- tion). 5. Let p be a prime number. Prove if pjab, then pja or pjb. 6. Let m be an integer. Show that the congruence class [a] has an inverse modulo m if and only if gcd(a;m) = 1. 7. Show that the operation [a]+[b] = [a+b] is well-dened. (So prove that the congruence class [a] + [b] doesn't depend on which representatives a and b are used.) 8. Show that congruence modulo m for any positive integer m is an equivalence rela- tion on the integers. (So let a; b be integers, show that aRb dened by a  b mod m is an equivalence relation.) 9. Let R be an equivalence relation on the set S. For any a and b in S, show that [a] = [b] if and only if aRb. 10. Let ff0; f1; f2; : : :g be the Fibonacci numbers. So f0 = 1 and f1 = 1 and fi = fi􀀀1+fi􀀀2 (So f2 = 2; f3 = 3 and f4 = 5 and so on.) Prove by induction that f1 + f3 + f5 + : : : + f2n+1 = f2n+2 􀀀 1: 11. Explain what the principle of induction is and how it works. 12. How is strong induction dierent from normal induction? 13. Dene Z m be the set of invertible elements in Zm and let m be a positive integer with gcd(2;m) = 1. a) Show that Z m and Z 2m have the same size. b) Dene f : Z 2m ! Z m by f(a[0]) = [b] where a  b mod m. Show f is injective (still assuming that gcd(2;m) = 1). c) Does f have an inverse? (Justify your answer.) 14. Assume f : X ! Y and g : Y ! Z. Show that if f and g have inverses then g  f also has an inverse. 15. Show that there is no bijection between the positive integers P and the interval [0; 1] = fx 2 R j 0  x  1g (recall that every number in this interval has a decimal expansion). 1