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

CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Extended Euclid
In this problem we will consider the extended Euclid’s algorithm. The bolded numbers below keep track of which numbers appeared as inputs to the gcd call. Remember that we are interested in writing the GCD as a linear combination of the original inputs, so we don’t want to accidentally simplify the expressions and eliminate the inputs.
(a) Note that x mod y, by definition, is always x minus a multiple of y. So, in the execution of Euclid’s algorithm, each newly introduced value can always be expressed as a “combination” of the previous two, like so:
gcd(2328, 440) = gcd(440, 128) = gcd(128,56)
= gcd(56,16) = gcd(16,8) = gcd(8,0) =8.
(Fill in the blanks)
(b) Recall that our goal is to fill out the blanks in
[128 = 1 × 2328 + (−5) × 440] [56 = 1×440+ ×128] [16 = 1×128+ ×56] [8 = 1×56+ ×16] [0 = 1×16+(−2)×8]
8= ×2328+ ×440.
To do so, we work back up from the bottom, and express the gcd above as a combination of the two
arguments on each of the previous lines:
8 = 1×8+0×0 = 1×8+(1×16+(−2)×8) = 1×16−1×8
= ×56+ ×16
[Hint: Remember, 8 = 1 × 56 + (−3) × 16. Substitute this into the above line.] = ×128+ ×56
[Hint: Remember, 16 = 1 × 128 + (−2) × 56.]
= ×440+ ×128
= ×2328+ ×440
(c) In the same way as just illustrated in the previous two parts, calculate the gcd of 17 and 38, and deter-
mine how to express this as a “combination” of 17 and 38.
CS 70, Fall 2021, DIS 4A 1
(d) What does this imply, in this case, about the multiplicative inverse of 17, in arithmetic mod 38?
2 Bijections
Let n be an odd number. Let f(x) be a function from {0,1,…,n−1} to {0,1,…,n−1}. In each of these cases say whether or not f (x) is necessarily a bijection. Justify your answer (either prove f (x) is a bijection or give a counterexample).
(a) f(x)=2x(modn). (b) f(x)=5x(modn). (c) n is prime and
􏰊0 if x=0, f(x)= x−1 (modn) if x̸=0.
(d) n is prime and f(x) = x2 (mod n).
3 Baby Fermat
Assume that a does have a multiplicative inverse mod m. Let us prove that its multiplicative inverse can be writtenasak (modm)forsomek≥0.
CS 70, Fall 2021, DIS 4A 2
(a) Consider the sequence a,a2,a3,… (mod m). Prove that this sequence has repetitions. (Hint: Consider the Pigeonhole Principle.)