Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 55 PRACTICE MIDTERM 2, FALL 2023

(1) Determine whether each statement below is true or false, and bubble in the circle next to (T) or (F) accordingly. You do NOT need to justify your answers.

(a) For any integers a and b and positive integer m, we have (a − b) mod m = a mod m − b mod m.

T ⃝ F ⃝

(b) If 99 students have a birthday in the next week (i.e. 7 days), then at least 15 of the students will have a birthday on the same day.

T ⃝ F ⃝

(c) There are 120 ways to put three distinguishable pigs (Paige, Patrick, Perry) into 6 distinct houses, if housemates are allowed.

T ⃝ F ⃝

(d) If a fair coin is flipped three times, the sample space is a set with 3 elements.

T ⃝ F ⃝

(e) The number of subsets of a set of cardinality 4 that have more than one element is 12.

T ⃝ F ⃝

(f) The number of injective functions from a set of 5 elements to a set of 6 elements is 6!

T ⃝ F ⃝

(2) (a) Let c, d, m be positive integers.

Show that if c mod m = d mod m then c ≡ d(mod m).

(b) Use the Euclidean algorithm to find the greatest common divisor of 2231 and 1843. Show your work below and put your final answer in this box:

(c) Find the inverse of 101 mod 9. Show your work below and put your final answer in this box:

(d) Prove by induction that for n ≥ 1, we have

(e) Prove that if p is a prime number, then p + 7 is not a prime number

(f) Let an = 1 if n = 1 or n = 2 and an = an−2 + 1 if n > 2. Show that

for all n ≥ 1.

(3) Find all solutions to the system of congruences x ≡ 2 (mod 3), x ≡ 3 (mod 4), x ≡ 3 (mod 5).

(4) Consider the set S of solutions to the equation x1 + x2 + x3 = 9, where each xi is a nonnegative integer.

(a) What is the cardinality of S?

(b) What is the probability that if we choose one of the solutions in S at random, we will have x1 ≥ 3

(5) Give a combinatorial proof of the identity