Mathematics 243, section 2 – Mathematical Structures Solutions for Exam 3 Review Problems November 29, 2017

Sample Exam Questions

Note: This list is longer than the actual exam will be to show the range of different kinds of questions that might appear. But the exam questions will be similar in content and format.

I. Consider an RSA public key cryptosystem with public information m = 143 and e = 37. A) “Crack the system” by determining the private information p, q and d.

Solution: The first step is that we need to factor m, here m = 143 = 11 · 13. The two primes are p = 11 and q = 13. (As we said before, the secure RSA systems used in the real world at the moment have primes p, q of around 200 decimal digits so this first step would be impractical, even with the current fastest computers and best software.) Then recall the encryption and decryption exponents are related by

e · d ≡ 1 mod (p − 1)(q − 1).

So we need to determine a multiplicative inverse for e = 37 in Z/120Z (since (11 − 1)(13−1) = 10·12 = 120). To do this we use the usual Euclidean algorithm approach:

\begin{aligned}120 & = 3 · 37 + 9 \\ 37 & = 4 · 9 + 1 \end{aligned}

Hence with the Extended Euclidean Algorithm table:

\begin{aligned}& 1  0 \\ & 0  1 \\ 3 & 1 − 3 \\ 4 & − 4 13 \end{aligned}

and the multiplicative inverse of e = 37 is d = 13. B) You intercept a message encrypted using this system consisting of the numbers 40, 114.

Use your answer to part A and the table on page 102 of the course notes to decrypt the message. Solution: We take

40^{13} mod 143 = 79

and

114^{13} mod 143 = 75

From the table, 79 ↔ “O′′ and 75 ↔ “K′′. The decrypted message is “OK” (not so valuable without knowing what the question was :). As a practical matter, to do calculations like this by hand, you would want to use repeated squaring. For instance

40^{2} ≡ 27 mod 143
40^{4} ≡ 27^{2} ≡ 14 mod 143
40^{8} ≡ 14^{2} ≡ 53 mod 143

Hence

40^{13} ≡ 40^{8} · 40^{4} · 40 ≡ 53 · 14 · 40 ≡ 79 mod 143.

II. A) Give the statement and proof of “Fermat’s Little Theorem.”

Solution: The statement is: If p is prime and gcd(a, p) = 1, then a^{p−1} ≡ 1 mod p. Here’s a sketch of the proof we did in class (try to fill in details for unproved statements yourself!). Since gcd(a, p) = 1, we know [a] has a multiplicative inverse mod p. This implies that the mapping f : (Z/pZ)^{×} → (Z/pZ)^{×} is both injective and surjective. Hence,

1 · 2 · · · · · (p − 1) ≡ a · (2a) · (3a) · · · · · (a(p − 1)) mod p

But the right side is just a^{p−1} · (1 · 2 · · · · · (p − 1)), so we have

(1)  x ≡ x · a^{p−1} mod p

where x = (p − 1)! = 1 · 2 · · · · · (p − 1). Now gcd(x, p) = 1 as well since all the factors are strictly less than p and p is prime. Hence x also has a multiplicative inverse mod p, and we can multiply both sides of (1) by that multiplicative inverse to get

1 ≡ a^{p−1} mod p,

which is what we wanted to show. B) Use part A to compute 3^{177} mod 7.

Solution: We have 3^{2} ≡ 2 mod 7, 3^{3} ≡ 6 mod 7, 3^{4} ≡ 4 mod 7, 3^{5} ≡ 5 mod 7 and 3^{6} ≡ 1 mod 7 (also by Fermat’s Little Theorem from part A). Therefore 3^{177} ≡ 3^{177 mod 6} ≡ 3^{3} ≡ 6 mod 7.

C) What is the smallest positive power k such that 7^{k} ≡ 1 mod 11? Same question for 5^{k} ≡ 1 mod 11. Solution: 7^{10} ≡ 1 mod 11 but no smaller positive power is congruent to 1 mod 11. 5^{5} ≡ 1 mod 11. This says k = 5 is the smallest such positive power.

III. Let f : A → B be a mapping. A) If S, T ⊆ A and f(S) ∩ f(T) ≠ ∅, can you conclude that S ∩ T ≠ ∅? (The answer is:

No). Why not? Give a counterexample. Solution: The answer is: No. The reason is that there is nothing here that would say f has to be injective. Let A = {a, b} (where a ≠ b) and let B = {y}, define f : A → B by making f(a) = y = f(b). If S = {a} and T = {b}, then S ∩ T = ∅, but f(S) = f(T) = {y} so f(S) ∩ f(T) ≠ ∅.

B) (continuing from A) Give a condition on f that would imply S ∩ T ≠ ∅ under the assumption that f(S) ∩ f(T) ≠ ∅. Prove your assertion. Solution: From the counterexample in part A, we expect that if f is assumed to be injective, then f(S)∩f(T) ≠ ∅, then S∩T ≠ ∅. To prove this suppose y ∈ f(S)∩f(T), then y = f(a) for some a ∈ S and also y = f(b) for some b ∈ T. But then f(a) = f(b). If f is injective, this implies a = b, so both are in S and in T, hence in S ∩ T.

C) If U, V ⊆ B and f^{−1}(U) ∩ f^{−1}(V) ≠ ∅, can you conclude that U ∩ V ≠ ∅? If so, prove it. If not, give a counterexample. Solution: Yes you can. If f^{−1}(U) ∩ f^{−1}(V) ≠ ∅, then there is some x ∈ f^{−1}(U) for which x ∈ f^{−1}(V) is also true. This means f(x) ∈ U and f(x) ∈ V, so U ∩ V ≠ ∅, since f(x) ∈ U ∩ V.

D) Show that f is surjective if and only if there is a mapping g : B → A such that f ∘ g = id_{B}. (id_{B} : B → B is the mapping satisfying id_{B}(y) = y for all y ∈ B.) Solution: ⇒: if f is surjective, then for each y ∈ B, there is some x ∈ A such that f(x) = y. Define g : B → A by saying g(y) = x where f(x) = y. If there is more than one possible x, just take any one of them and use that to define g. But now if y ∈ B is arbitrary (f ∘ g)(y) = f(g(y)) = f(x) = y. Hence f ∘ g = id_{B}. ⇐: If there is a g such that f ∘ g = id_{B}, then for all y ∈ B, y = id_{B}(y) = (f ∘ g)(y) =

f(g(y)). But this says that f(x) = y where x = g(y) ∈ A. Hence g is surjective because y ∈ B was arbitrary.

IV. A) The binomial coefficient \binom{n}{k} is the number of subsets of A = \{a_{1}, …, a_{n}\} that contain

exactly k elements. Assuming this fact, give (yet another) proof that A has 2^{n} distinct subsets (including ∅ and A itself). Solution: The Binomial Theorem says

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k}.

Substitute x = y = 1 to get

2^{n} = ∑_{k=0}^{n} \binom{n}{k}1^{k} · 1^{n−k} = ∑_{k=0}^{n} \binom{n}{k}.

There are \binom{n}{k} different ways to select a subset of A containing exactly k elements for each k = 0, …, n. This accounts for all of the subsets since every subset has one of these integers k as its number of elements. Hence the number of subsets is the sum, which equals 2^{n}.

B) Show by mathematical induction: For all u > 0 in the reals, and all n ≥ 0,

1 + nu + \frac{n(n − 1)}{2}u^{2} + \frac{n(n − 1)(n − 2)}{6}u^{3} ≤ (1 + u)^{n}

Solution: The idea is the same as Exercise 9.18 from Problem Set 8. For the induction step, use the induction hypothesis like this:

(1 + u)^{k+1} = (1 + u)^{k} · (1 + u) ≥ (1 + ku + \frac{k(k − 1)}{2}u^{2} + \frac{k(k − 1)(k − 2)}{6}u^{3}) (1 + u)

Multiply out and simplify. You will see that the result is

1 + (k + 1)u + \frac{(k + 1)k}{2} u^{2} + \frac{(k + 1)k(k − 1)}{6}u^{3} + (positive)

This implies the statement with n = k + 1. C) Give a second proof of the statement in part B using the Binomial Theorem.

Solution: See part B Exercise 9.18 from Problem Set 8. This follows because the

1 + nu + \frac{n(n − 1)}{2}u^{2} + \frac{n(n − 1)(n − 2)}{6}u^{3}

exactly equals the first four terms in the binomial expansion of (1 + u)^{n} and the remaining terms are all non-negative.

V. A) Prove that N is not bounded above in the real numbers. Use this to deduce that for

any ε > 0, there exists n ≠ 0 ∈ N such that \frac{1}{n} < ε. Solution: Suppose on the contrary that N is bounded above in R. Then the Completeness Axiom implies that N has a least upper bound, say B. Since B −1 < B, this would imply that there must be a natural number n ∈ N satisfying B − 1 < n ≤ B. However given n, n + 1 ∈ N as well, and by adding 1 to the two terms on the left in the last inequalities, B < n + 1. This contradicts the choice of B since B was supposed to be an upper bound for N. For the second part, if ε > 0, then 1/ε is not an upper bound for N, so there exists n ∈ N with n > 1/ε. Since n, 1/ε > 0, this implies 1/n < ε, which is what we wanted to show.

B) Use the last statement in part A to prove that the sequence a_{n} = 3 − \frac{1}{n} converges to L = 3. Solution: Let ε > 0 and use the previous part to find n_{0} ∈ N such that 1/n_{0} < ε. Then for any n ≥ n_{0} we have

|(3 − \frac{1}{n}) − 3| = \frac{1}{n} ≤ \frac{1}{n_{0}} < ε.

This shows that a_{n} converges to 3 by the definition. C) Prove that a_{n} = 3 − \frac{1}{\sqrt{n}} also converges to L = 3.

Solution: Let ε > 0 and use the previous part to find n_{0} ∈ N such that 1/n_{0} < ε^{2}. This implies n_{0} > 1/ε^{2}, so \sqrt{n_{0}} > 1/ε and 1/\sqrt{n_{0}} < ε. Then for any n ≥ n_{0} we have

|(3 − \frac{1}{\sqrt{n}}) − 3| = \frac{1}{\sqrt{n}} ≤ \frac{1}{\sqrt{n_{0}}} < ε.

This shows that a_{n} converges to 3 by the definition.

VI. Let R be the relation on the set of real numbers defined by aRb if and only if a−b ∈ Z. For example 1.32R(−5.68) is true for this relation since 1.32 − (−5.68) = 7 ∈ Z. A) Show that R is an equivalence relation.

Solution:

• R is reflexive since for every real number x, x − x = 0 ∈ R.

• R is symmetric since if xRy, then x − y ∈ Z, so −(x − y) = y − x ∈ Z as well. (The set of integers is closed under taking additive inverses.) This shows yRx.

• R is transitive since if xRy and yRz, then x − y and y − z are integers. Adding, we get (x − y) + (y − z) is also an integer, because Z is closed under sums. Hence x − z is an integer, and this shows xRz, which shows R is transitive.

B) Show that the functions sin(2πx) and cos(2πx) are well-defined mod R. Solution: This follows by the periodicity of sin and cos: Suppose xRx′, so x − x′ = k ∈ Z. Then x = x′ + k, so

sin(2πx) = sin(2π(x′+k)) = sin(2πx′+2πk) = sin(2πx′) cos(2πk)+sin(2πk) cos(2πx′),

using the addition formula for the sine. But cos(2πk) = 1 and sin(2πk) = 0 for all k ∈ Z. Hence sin(2πx) = sin(2πx′). This shows sin is well-defined mod R. The proof for cos is similar.

C) Give a subset of R that contains a unique element from each of the equivalence classes for the relation R. (That is, your set should contain a’s “hitting” all of the equivalence classes, but each one only once. Solution: One such set is the interval [0, 1) = {x ∈ R : 0 ≤ x < 1}. If x, x′ ∈ [0, 1), then |x − x′| < 1, so x − x′ cannot be an integer, and x and x′ are not related for this relation. On the other hand if x is any real number, then we can write x = k +x′ with k = [x] ∈ Z and x′ ∈ [0, 1). (k would be called the greatest integer less than or equal to x, and at least if x > 0, x′ would be called the fractional part of x). This implies xRx′, so the equivalence classes of the x′ ∈ [0, 1) account for all the equivalence classes.