CS 70 Discrete Mathematics and Probability Theory: Final Exam 2025/26 Solutions -University of California, Berkeley.

CS 70 Discrete Mathematics and Probability Theory
Spring 2025 Rao Final Solutions
P RINT Your Name: Oski Bear

S IGN Your Name: OS K I



Do not turn this page until your instructor tells you to do so.




CS 70, Spring 2025, Final Solutions 1

, SID:


1. Pledge.
Berkeley Honor Code: As a member of the UC Berkeley community, I act with honesty, integrity, and
respect for others.
In particular, I acknowledge that:

• I alone am taking this exam. Other than with the course staff, I will not have any verbal, written, or
electronic communication about the exam with anyone else while I am taking the exam or while others
are taking the exam.
• I will not refer to any books, notes, or online sources of information while taking the exam, other than
what the instructor has allowed.
• I will not take screenshots, photos, or otherwise make copies of exam questions to share with others.


S IGN Your Name:


2. Warmup.
(1 point) May 16th is a special day: not only is it the day of the Spring 2025 CS70 final exam, but it is also
which TA’s birthday? (Hint: It may help to read through the entire exam!)
Answer: Jay: this is mentioned in the last question of the exam!

3. Propositional Logic

1. Let P, Q and R be propositions.
(a) (P =⇒ ¬Q) ≡ (¬P ∨ ) (Fill in the blank to make the statement always true.)
Answer: ¬Q. We have that P =⇒ Q ≡ ¬P ∨ Q, so in this case, we have that P =⇒ ¬Q ≡
¬P ∨ ¬Q.
(b) P ∧ (Q ∨ R) ≡ (P ∨ Q) ∧ (P ∨ R).
Answer: False. Suppose P is False, then the LHS must be False, but if Q and R are both true,
then the RHS is True.
(c) P ∧ (¬P ∨ Q) ∧ (¬P ∨ ¬Q)
Answer: Always false.
If P is false, then the whole proposition is immediately false. Elsewise, if P is true, then both
(¬P∨Q) and (¬P∨¬Q) can be simplified to (False ∨Q) ≡ Q and (False ∨¬Q) ≡ ¬Q respectively.
We can see that these cannot both be true simultaneously, and thus their conjunction must be False.
2. Let P(n) and Q(n) are propositions over n ∈ N.
(a) Suppose the following is true:

(∀n ∈ N)(P(n) =⇒ Q(n + 1)) ∧ (∀n ∈ N)(Q(n) =⇒ P(n + 1)) ∧ P(0)

Determine whether the following statements are true or false.
i. (∀n ∈ N)(2 | n =⇒ P(n))
Answer: True. P(n) =⇒ Q(n + 1) =⇒ P(n + 2) and P(0), or P(0) and P(2i) =⇒ P(2(i +
1)), which by the principle of induction is true for all i.
ii. (∀n ∈ N)(¬Q(n + 1) =⇒ ¬P(n))
Answer: True. This is the contrapositive of P(n) =⇒ Q(n + 1).

2

, SID:


iii. Q(0) =⇒ (∀n ∈ N)(Q(n)).
Answer: True, the original propositions make all even P(n) true and all odd Q(n) true, and
having Q(0) be true as well fills the rest of the inductive gaps.
(b) ¬(∀n ∈ N)(P(n) ∨ Q(n)) =⇒ (∃n ∈ N)(¬P(n)).
Answer: True. There must be a value of n where both P(n) and Q(n) are false.

4. Proofs

1. (8 points) Suppose p and q are distinct primes larger than 2.
Prove that if e ≡ d −1 (mod (p − 1)(q − 1)), then xed ≡ x (mod pq).
(You are welcome to use the Chinese Remainder Theorem and/or Fermat’s Little Theorem, but simply
asserting this is true from the fact that RSA works properly will earn 0 points.)
Answer: Since ed ≡ 1 (mod (p − 1)(q − 1)), we know that ed = k(p − 1)(q − 1) + 1.
This means that we’d like to show that

xed ≡ xk(p−1)(q−1)+1 ≡ x (mod pq)
k(p−1)(q−1)+1
x − x ≡ 0 (mod pq)
x(xk(p−1)(q−1) − 1) ≡ 0 (mod pq)

Let us consider this equivalence under mod p and under mod q separately.
Under mod p, we want to look at x(xk(p−1)(q−1) − 1) (mod p). Note that there are only two ways in
which this expression can be zero: either x ≡ 0 (mod p), or xk(p−1)(q−1) − 1 ≡ 0 (mod p). Hence, if
x ≡ 0 (mod p), we immediately find that this expression is equivalent to 0; as such, we’ll focus on the
case where x ̸≡ 0 (mod p).
Here, we’d like to show that xk(p−1)(q−1) ≡ 1 (mod p). Since x ̸≡ 0 (mod p), we have by FLT that

xk(p−1)(q−1) = (x p−1 )k(q−1) (mod p)
≡ 1k(q−1) ≡ 1 (mod p)

which shows that xk(p−1)(q−1) − 1 ≡ 0 (mod p) as desired.
The same argument applies under mod q; the expression is equivalent to 0 immediately if x ≡ 0
(mod q), and otherwise for x ̸≡ 0, we have by FLT that

xk(p−1)(q−1) = (xq−1 )k(p−1) (mod q)
k(p−1)
≡1 ≡ 1 (mod q)

This means that we have the system
(
x(xk(p−1)(q−1) − 1) ≡ 0 (mod p)
=⇒ x(xk(p−1)(q−1) ) ≡ 0 (mod pq)
x(xk(p−1)(q−1) − 1) ≡ 0 (mod q)

by CRT, completing the proof.
2. A graph H = (VH , EH ) is a subgraph of another graph G = (VG , EG ) if there exists an injective function
h : VH → VG mapping vertices in H to vertices in G, such that each edge (u, v) ∈ EH corresponds to an
edge (h(u), h(v)) ∈ EG .
There is only one tree on three vertices; the length two path:

3