MATH 127: Sample Exam 3B
Wednesday, November 20, 2024
1. (a) Let m be a positive integer and suppose that for some n ∈ Z, m | 8n+3 and m | 5n+2.
Determine (with proof) all possible values of m. [7 pts]
(b) Let m be a positive integer such that 4 · 5 ≡ −4 (mod m) but 3 + 6 ≢ 1 (mod m).
Determine (with proof) all possible values of m. [8 pts]
2. (a) Give an example of distinct uncountable sets A and B such that A 、B is countably infinite. Simply state your sets A, B, and A 、B. No further justification is required. [5 pts]
(b) Give an example of distinct uncountable sets A and B such that A ∩ B is uncountable.
Simply state your sets A, B, and A ∩ B. No further justification is required. [5 pts]
(c) Give an example of distinct uncountable sets A and B such that A△B is finite and nonempty. Simply state your sets A, B, and A△B. No further justification is required.
Recall: A△B = (A 、B) ∪ (B 、A) is the symmetric difference. [5 pts]
3. (a) Compute φ(63) [5 pts]
(b) Suppose n ∈ Z with gcd(n,63) = 1. Which of the following are possible orders of n modulo 63? Circle all that apply. [5 pts]
(i) 4 (ii) 63
(iii) 36 (iv) 6
(v) 1 (vi) -2
(c) Determine the order of 5 modulo 63. [5 pts]
(d) Find the least nonnegative residue of the inverse of 5 modulo 63. [8 pts]
(e) Find the least x ∈ N satisfying the congruence 40x ≡ 56 (mod 63). [8 pts]
4. Construct a bijection between P(N) and P(N)∖{∅ }. Prove that your function is a bijection.
You do not need to prove well-definedness. [24 pts]
5. Prove that for any a,b ∈ Z, if 3 ∤ a and gcd(a,b) = 1 then gcd(a + 3b,ab) = 1. [15 pts]