## Transcribed Text

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

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.