CS 70 Spring 2017 1
Discrete Mathematics and Probability Theory Rao
HW 5
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 x≡4
(mod 5) (mod 7).
(1)
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