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.)
(b)Assumingthatai≡aj (modm),wherei>j,whatcanyousayaboutai−j (modm)?
(c) Prove that the multiplicative inverse can be written as ak (mod m). What is k in terms of i and j?
CS 70, Fall 2021, DIS 4A 3
4 Euler’s Totient Function
Euler’s totient function is defined as follows: φ(n)=|{i:1≤i≤n,gcd(n,i)=1}|
In other words, φ(n) is the total number of positive integers less than or equal to n which are relatively prime to it. Here is a property of Euler’s totient function that you can use without proof:
For m,n such that gcd(m,n) = 1, φ(mn) = φ(m)·φ(n). (a) Let p be a prime number. What is φ(p)?
(b) Let p be a prime number and k be some positive integer. What is φ(pk)?
(c) Let p be a prime number and a be a positive integer smaller than p. What is aφ(p) (mod p)? (Hint: use Fermat’s Little Theorem.)
(d) Letbbeapositiveintegerwhoseprimefactorsarep1,p2,…,pk.Wecanwriteb=pα1·pα2…pαk. 12k
Show that for any a relatively prime to b, the following holds:
∀i ∈ {1,2,…,k}, aφ(b) ≡ 1 (mod pi)
CS 70, Fall 2021, DIS 4A