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
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
This is only a preview of the solution. Please use the purchase button to see the entire solution
$50.00 for this solution
Sorry, there was an error processing your request
Sorry, there was a problem with your payment. Please try again or try another payment method.
PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.
Please let us know the date by which you need help from your tutor or the date and time you wish to have an online tutoring session.
Request Speed
Normal response time: Our most experienced, most successful tutors are provided for maximum expertise and reliability.
Fast response time: Used only for emergencies when speed is the single most important factor.
Why do we ask for this?
We require your email address so that we can send you an email alert when the tutor responds to your message.
We respect your privacy. Your email address will not be used for any other purpose.
You may read our privacy policy for more info.
Please use a personal email address
Please use an email address that does not end in .edu.
This is not a free service
You will get a negotiable price quote with no obligation.
Homework Due Date
Please let us know the date by which you need help from your tutor or the date and time you wish to have an online tutoring session.
Request Speed
Normal response time: Our most experienced, most successful tutors are provided for maximum expertise and reliability.
Fast response time: Used only for emergencies when speed is the single most important factor.
Why do we ask for this?
We require your email address so that we can send you an email alert when the tutor responds to your message.
We respect your privacy. Your email address will not be used for any other purpose.
You may read our privacy policy for more info.
This is not a free service
You will get a negotiable price quote with no obligation.
Homework Library
Warning: If you try using the HL in an unethical manner, expect to fail your class. All HL items are old, recycled materials and are therefore not original. We intend them to be used only for the purpose of studying and learning.