Discrete Mathematics (Dow) -- Test 1 Version C In all questions, clear reasoning must be provided. 1. Perform the indicated computations (in (a)-(c) your answer should be between 0 and m-1). 1. 12^2 * 13 mod 11 12 is just 1 and 13 is just 2 mod 11, so we have 1^2 * 2 = 2 2. -40 mod 13 (use == for 'congruent modulo') -40 == -40 + 13 = -27 == -27 + 13 = -14 == -1 == 12 3. 3 * (5600000002) mod 56 5600000002 = 5600000000 + 2 == 2 mod 56, so answer is 6 4. 17 is inverse of 2 mod m . What are the possible values of m. Well, 17 * 2 == 1 (mod m), i.e. 34 == 1 (mod m), i.e. 33 == 0 (mod m) The only values for m then are 1, 3, 11, 33 2. In this question we are only interested in values of x between 0 and the modulus m. You must justify your answers. 1. 3x==5(mod 7) . Find all solutions. Inspection is fine: x=4 gives 3x=12 which is congruent mod 7 to 5 2. 4x==6 (mod 402) . Is there 0, 1, or more than one solution? I wanted, gcd(4,402) = 2 (I thought it easy: 402/2 = 201 so 4 doesn't divide). Then 2 does divide 6 so there is a solution and since gcd > 1, there is more than one. 3. 6x==4(mod 3333) . Is there 0, 1, or more than one solution? I thought it obvious that gcd(6,3333)=3 and 3 doesn't divide 4 so there's no solutions. 3. Throughout this question replace d by the value that you obtain in Part (a). (a) Express d=gcd(65,91) as a linear combination of 65 and 91. First go through Euclidean algorithm: 91=1*(65)+26 and 65 = 2*(26) + 13 and 26 = 2(13) so d=13 is the gcd. Now 13 = 65 - 2(26) and 26 = 91 -1*(65) plug the second equation into the first 13 = 65 - 2(26) = 65 - 2(91-65) = simplify = 65 -2(91) + 2(65) hence 13 = 3(65) - 2(91) (b) Explain how to use your answer in Part (a) to solve 65 y == d (mod 91) Well just use the coefficient 3=y since 3(65)= 13 + 2(91). (c) Is there an x which is a solution to the system x==0(mod 65) and x==d(mod 91) Yes, x==0 (mod 65) means that x = 65 t for some integer t. Then x==d (mod 91) means that t is such that x=65 t == d (mod 91) well, we know the solution for t, it is 3. So finally x = 65*3. 4. Consider the function f(n) = n^2 + (-1)^n * (n^2-10). 1. Compute some values (n even), (n odd). I wanted you to pick up the pattern that f(n) = 2*n^2 - 10 for n even, and f(n) = 10 for n odd 2. Find the smallest integer m such that is O(n^m). As hinted, |f(n)| <= 2*n^2+10 for all n and this is clearly O(n^2), hence f(n) is O(n^2). 3. Find the largest j such that n^j is O(f(n)) . Well the value of j is just 0, because even with j=1, n is not O(f(n)) because for all those odd integers n, f(n) is just 10 which means there is no constant C such that n < C*10 for all odd n. 5. The following algorithm uses m as a moduli, and a, c as seeds to generate a sequence of pseudorandom numbers. For each i, it uses the binary search algorithm to test which of the are in the (increasing) list . Discuss the worst case big-O complexity. Of course we know that the binary search algorithm is O so take that for granted in your computations. Procedure Random Test (m,a,c : integers;a_1,...,a_n :increasing integers) x:=1 random := 0 for k:= 1 to n begin x:= a*x + c (mod m) {this is what we called x_k} i:= Binary Search(x,a_1,...,a_n) if x=a_i then random := random +1 end The variable k runs from 1 to n. For each value of k, there are log(n)+3 many steps between begin and end because we assume the binary search algorithm takes log(n) steps. Adding this up we get log(n) + log(n) + ... + log(n) (n times) hence O(n log(n) ). Alan Dow Wed Oct 16 10:23:19 EDT 1996

Wed Oct 16 12:45:38 EDT 1996