CS代考 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写

CS 70 Discrete Mathematics and Probability Theory Fall 2021
Due: Friday 9/24, 10:00 PM Grace period until Friday 9/24 11:59 PM
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Modular Practice
Solve the following modular arithmetic equations for x and y.
(a) 9x+5 ≡ 7 (mod 11).
(b) Show that 3x + 15 ≡ 4 (mod 21) does not have a solution.
(c) The system of simultaneous equations 3x + 2y ≡ 0 (mod 7) and 2x + y ≡ 4 (mod 7). (d) 132019 ≡ x (mod 12).
(e) 721 ≡ x (mod 11).
(f) x≡5 (mod 7),x≡3 (mod 9),x≡3 (mod 11). Whatisthesmallestpossiblevalueforx? 2 Check Digits: ISBN
In this problem, we’ll look at a real-world applications of check-digits.
International Standard Book Numbers (ISBNs) are 10-digit codes (d1d2 …d10) which are assigned
by the publisher. These 10 digits contain information about the language, the publisher, and the
number assigned to the book by the publisher. Additionally, the last digit d10 is a “check digit”
selected so that ∑10 i · di ≡ 0 (mod 11). (Note that the letter X is used to represent the number 10 i=1
in the check digit.)
(a) Suppose you have a very worn copy of the (recommended) textbook for this class. You want to list it for sale online but you can only read the first nine digits: 0-07-288008-? (the dashes are only there for readability). What is the last digit? Show your work.
CS 70, Fall 2021, HW 4 1
(b) (c) (d)
Wikipedia says that you can determine the check digit by computing ∑9i=1 i · di (mod 11). Show that Wikipedia’s description is equivalent to the above description.
Prove that changing any single digit of the ISBN will render the ISBN invalid. That is, the check digit allows you to detect a single-digit substitution error.
Can we ever switch two distinct digits in an ISBN number and get another valid ISBN number? For example, could 012345678X and 015342678X both be valid ISBNs? Explain.
Divisible or Not
Prove that for any number n, the number formed by the last two digits of n are divisible by 4 if and only if n is divisible by 4. (For example, ‘23xx’ is divisible by 4 if and only if the number ‘xx’ is divisible by 4.)
Prove that for any number n, the sum of the digits of n are divisible by 3 if and only if n is divisible by 3.
Just Can’t Wait
Joel lives in Berkeley. He mainly commutes by public transport, i.e., bus and BART. He hates waiting while transferring, and he usually plans his trip so that he can get on his next vehicle immediately after he gets off the previous one (zero transfer time, i.e. if he gets off his previous vehicle at 7:00am he gets on his next vehicle at 7:00am). Tomorrow, Joel needs to take an AC Transit bus from his home stop to the Downtown Berkeley BART station, then take BART into San Francisco.
The bus arrives at Joel’s home stop every 22 minutes from 6:05am onwards, and it takes 10 minutes to get to the Downtown Berkeley BART station. The train arrives at the station every 8 minutes from 4:25am onwards. What time is the earliest bus he can take to be able to transfer to the train immediately? Show your work. (Find the answer without listing all the schedules. Hint: derive an equation relating the bus number and train number and then work in modular arithmetic to get rid of one of the variables to give a set of possible train numbers.)
Joel has to take a Muni bus after he gets off the train in San Francisco. The commute time on BART is 33 minutes, and the Muni bus arrives at the San Francisco BART station every 17 minutes from 7:12am onwards. What time is the earliest bus he could take from Berkeley to ensure zero transfer time for both transfers? If all bus/BART services stop just before midnight, is it the only bus he can take that day? Show your work.
Fermat’s Little Theorem
Fermat’s Little Theorem states that for any prime p and any a ∈ {1,2,…, p−1}, we have ap−1 ≡ 1 (mod p). Without using induction, prove that ∀n ∈ N, n7 − n is divisible by 42.
CS 70, Fall 2021, HW 4 2
6 Sparsity of Primes
A prime power is a number that can be written as pi for some prime p and some positive integer i. So,9=32 isaprimepower,andsois8=23. 42=2·3·7isnotaprimepower.
Prove that for any positive integer k, there exists k consecutive positive integers such that none of them are prime powers.
Hint: this is a Chinese Remainder Theorem problem. We want to find x such that x + 1;x + 2;x + 3; : : :x+k are all not powers of primes. We can enforce this by saying that x+1 through x+k each must have two distinct prime divisors.
7 Unique Prime Factorization
We proved in lecture that every positive integer has a factorization into primes. Using the tech- niques in this course, we can show that this factorization is unique, up to reordering the factors!
Recall from lecture that we defined a prime number p to be a positive integer whose only positive factors are 1 and p.
In this problem, you should not assume that the positive integers have unique prime factor- ization.
(a) Let p and q be distinct primes. Show that p 􏰎 q.
(b) Provethatifaandbarepositiveintegerssuchthat p|ab,then p|aor p|b. (Hint: Usethe
Extended Euclidean algorithm: There are integers x, y such that ax + py = gcd(a, p).)
(c) Show that the prime factorization of a positive integer n is unique up to reordering the factors. (Hint: Suppose that there were two prime factorizations of n. Use the previous parts to show that the factorizations are the same.)
8 Wilson’s Theorem
Wilson’s Theorem states the following is true if and only if p is prime: (p−1)!≡−1 (mod p).
Prove both directions (it holds if AND only if p is prime).
Hint for the if direction: Consider rearranging the terms in (p − 1)! = 1 · 2… · p − 1 to pair up
terms with their inverses, when possible. What terms are left unpaired?
Hint for the only if direction: If p is composite, then it has some prime factor q. What can we say
about(p−1)! (modq)?
CS 70, Fall 2021, HW 4 3