MATH 127: Sample Exam 3A
Wednesday, November 20, 2024
1. Let m = 28 · 33 · 54 · 113 and n = 22 · 36 · 72 · 11.
(a) Determine gcd(m,n) and lcm[m,n]. You do not need to simplify your answers. [6 pts]
(b) Find the smallest integer x > 1 such that x is coprime to m. [4 pts]
(c) Determine the number of odd positive integers that divide both m and n. [6 pts]
(d) Determine the number of integers x ∈ [m] such that x is invertible modulo m. You do not need to simplify your answer. [6 pts]
2. For each of the following sets, determine whether it is countable or uncountable. Provide a brief justification (1–2 lines). [18 pts]
(a) A = {(n,x) ∈ Z+ × R | x = ln(n)}
(b) B = (Z × {0}) ∪ (R × {1})
(c) C = N × Z × P(N) × P(Z)
3. (a) Use the Euclidean algorithm to calculate gcd(231 , 91). [6 pts]
(b) Use the extended Euclidean algorithm to find an ordered pair (m,n) ∈ Z2 such that 231m + 91n = gcd(231, 91). [5 pts]
(c) Find all x ∈ Z such that 91x ≡ 63 (mod 231). [10 pts]
(d) Find all x ∈ Z such that 91x ≡ 63 (mod 231) and x has a remainder of 2 when divided by 5. [8 pts]
4. Prove that for all m,n ∈ Z+ and all a,b,c ∈ Z, if a ≡ c (mod m) and b ≡ c (mod n) then a ≡ b (mod gcd(m,n)) [15 pts]
5. Let S = (0, 5) and T = [0, 3) ∪ (3, 5]. Use the Cantor-Bernstein-Schroeder Theorem to prove that |S| = |T| .
You do not need to prove your functions are well-defined, but prove any other necessary properties. [16 pts]