CS 70 Discrete Mathematics and Probability Theory
Spring 2017 Rao HW 5
1 Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up. (Signature here)
2 Count and Prove
(a) Over 1000 students walked out of class and marched to protest the war. To count the exact
number of students protesting, the chief organizer lined the students up in columns of different
length. If the students are arranged in columns of 3, 5, and 7, then 2, 3, and 4 people are left
out, respectively. What is the minimum number of students present? Solve it with Chinese
Remainder Theorem.
(b) Prove that for n ≥ 1, if 935 = 5 × 11 × 17 divides n80 − 1, then 5, 11, and 17 do not divide n.
Solution:
(a) Let the number of students be x. The problem statement allows us to write the system of
congruences:
x≡2 (mod 3)
x≡3 (mod 5) (1)
x≡4 (mod 7).
To apply CRT, we first find the multiplicative inverse of 5 × 7 modulo 3, which is 2. This gives
us
y1 = (5 × 7) × (5 × 7)−1 (mod 3) = 35 × 2 = 70.
CS 70, Spring 2017, HW 5 1
, Second, we compute the multiplicative inverse of 3 × 7 modulo 5, which is 1. We have
y2 = (3 × 7) × (3 × 7)−1 (mod 5) = 21 × 1 = 21.
Finally, the the multiplicative inverse of 3 × 5 modulo 7 is 1. Thus,
y3 = (3 × 5) × (3 × 5)−1 (mod 7) = 15 × 1 = 15.
By CRT, we can write down the unique solution x (modulo 105 = 3 × 5 × 7):
x = a1 y1 + a2 y2 + a3 y3 (mod 105)
= 2 × 70 + 3 × 21 + 4 × 15 (mod 105)
= 263 (mod 105)
= 53 (mod 105).
Now, we have x = 105k + 53 for some integer k. The smallest k for x > 1000 is 10. Thus, the
mininum number of students is 105 × 10 + 53 = 1103.
(b) Note that 935 = 5 × 11 × 17. We wish to prove that if n80 ≡ 1 (mod 935) then 5, 11, 17 - n.
Since n80 ≡ 1 (mod 935), we know that n80 = 935k + 1 for some integer k. Thus, we know
n80 ≡ 1 (mod 5), n80 ≡ 1 (mod 11), and n80 ≡ 1 (mod 17).
We will now prove the statement by contradiction. Let us now assume the contrary; i.e., that
n80 ≡ 1 (mod 935) and either 5 | n or 11 | n or 17 | n. Then we have 3 possible cases:
• If 5 | n then, n = 5k, which implies n ≡ 0 (mod 5), which in turn implies n80 ≡ 0
(mod 5),
• If 11 | n then, n = 11k, which implies n ≡ 0 (mod 11), which in turn implies n80 ≡ 0
(mod 11),
• If 17 | n then, n = 17k, which implies n ≡ 0 (mod 17), which in turn implies n80 ≡ 0
(mod 17),
which are all false as under the assumptions that n80 ≡ 1 (mod 935), since this implies n80 ≡ 1
(mod 5), n80 ≡ 1 (mod 11), and n80 ≡ 1 (mod 17). Thus we have reached a contradiction,
and we must have that 5, 11, 17 - n.
3 RSA Lite
Woody misunderstood how to use RSA. So he selected prime P = 101 and encryption exponent
e = 67, and encrypted his message m to get 35 = me mod P. Unfortunately he forgot his original
message m and only stored the encrypted value 35. But Carla thinks she can figure out how to
recover m from 35 = me mod P, with knowledge only of P and e. Is she right? Can you help her
figure out the message m? Show all your work.
Solution:
CS 70, Spring 2017, HW 5 2
Spring 2017 Rao HW 5
1 Sundry
Before you start your homework, write down your team. Who else did you work with on this
homework? List names and email addresses. (In case of homework party, you can also just describe
the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for
your "Sundry" grade.
Please copy the following statement and sign next to it:
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up.
I certify that all solutions are entirely in my words and that I have not looked at another student’s
solutions. I have credited all external sources in this write up. (Signature here)
2 Count and Prove
(a) Over 1000 students walked out of class and marched to protest the war. To count the exact
number of students protesting, the chief organizer lined the students up in columns of different
length. If the students are arranged in columns of 3, 5, and 7, then 2, 3, and 4 people are left
out, respectively. What is the minimum number of students present? Solve it with Chinese
Remainder Theorem.
(b) Prove that for n ≥ 1, if 935 = 5 × 11 × 17 divides n80 − 1, then 5, 11, and 17 do not divide n.
Solution:
(a) Let the number of students be x. The problem statement allows us to write the system of
congruences:
x≡2 (mod 3)
x≡3 (mod 5) (1)
x≡4 (mod 7).
To apply CRT, we first find the multiplicative inverse of 5 × 7 modulo 3, which is 2. This gives
us
y1 = (5 × 7) × (5 × 7)−1 (mod 3) = 35 × 2 = 70.
CS 70, Spring 2017, HW 5 1
, Second, we compute the multiplicative inverse of 3 × 7 modulo 5, which is 1. We have
y2 = (3 × 7) × (3 × 7)−1 (mod 5) = 21 × 1 = 21.
Finally, the the multiplicative inverse of 3 × 5 modulo 7 is 1. Thus,
y3 = (3 × 5) × (3 × 5)−1 (mod 7) = 15 × 1 = 15.
By CRT, we can write down the unique solution x (modulo 105 = 3 × 5 × 7):
x = a1 y1 + a2 y2 + a3 y3 (mod 105)
= 2 × 70 + 3 × 21 + 4 × 15 (mod 105)
= 263 (mod 105)
= 53 (mod 105).
Now, we have x = 105k + 53 for some integer k. The smallest k for x > 1000 is 10. Thus, the
mininum number of students is 105 × 10 + 53 = 1103.
(b) Note that 935 = 5 × 11 × 17. We wish to prove that if n80 ≡ 1 (mod 935) then 5, 11, 17 - n.
Since n80 ≡ 1 (mod 935), we know that n80 = 935k + 1 for some integer k. Thus, we know
n80 ≡ 1 (mod 5), n80 ≡ 1 (mod 11), and n80 ≡ 1 (mod 17).
We will now prove the statement by contradiction. Let us now assume the contrary; i.e., that
n80 ≡ 1 (mod 935) and either 5 | n or 11 | n or 17 | n. Then we have 3 possible cases:
• If 5 | n then, n = 5k, which implies n ≡ 0 (mod 5), which in turn implies n80 ≡ 0
(mod 5),
• If 11 | n then, n = 11k, which implies n ≡ 0 (mod 11), which in turn implies n80 ≡ 0
(mod 11),
• If 17 | n then, n = 17k, which implies n ≡ 0 (mod 17), which in turn implies n80 ≡ 0
(mod 17),
which are all false as under the assumptions that n80 ≡ 1 (mod 935), since this implies n80 ≡ 1
(mod 5), n80 ≡ 1 (mod 11), and n80 ≡ 1 (mod 17). Thus we have reached a contradiction,
and we must have that 5, 11, 17 - n.
3 RSA Lite
Woody misunderstood how to use RSA. So he selected prime P = 101 and encryption exponent
e = 67, and encrypted his message m to get 35 = me mod P. Unfortunately he forgot his original
message m and only stored the encrypted value 35. But Carla thinks she can figure out how to
recover m from 35 = me mod P, with knowledge only of P and e. Is she right? Can you help her
figure out the message m? Show all your work.
Solution:
CS 70, Spring 2017, HW 5 2
