Discrete Mathematics (Dow) -- Test 1 Version D In all questions, clear reasoning must be provided. 1. For (a) - (c), find an answer between 0 and m-1. For part (d) either complete the explanation or find the fault in the reasoning. 1. (-3)* 51 (mod 15) (use == for congruent) 51 is just 6 mod 15, so (-3)*51 == (-3)*6 == -18 == -3 == 12 2. 36 * 17 mod 12 36 is just 0 mod 12, so we get 0 as the answer (0*17 = 0) 3. (101)^18 mod 10 101 is just 1 mod 10, so (101)^18 == 1^18 = 1 4. x=11 is not a solution to 10x==2 (mod 12) since dividing both sides by 2 yields 5x==1(mod 12). We can check that x=11 is not a solution of as follows... Well, x=11 IS a solution to 10x==2(mod 12) and the flaw is simply that we cannot cancel the 2 (or divide) because gcd(2,12) > 1 2. In this question we are only interested in values of x between 0 and the modulus m. You must justify your answers. 1.5x==1 (mod 7) -- Find all solutions. Inspection x=3 is fine 2. 6x==3(mod 999) -- Is there 0, 1, or more than one solution? I expected: gcd(6,999) is obviously 3 and 3 does divide 3 so there is a solution. Also since gcd(6,999)>1, there is more than one solution. 3. 6x==4 (mod 999)-- Is there 0, 1, or more than one solution? Now no solution since gcd(6,999) does not divide 4. 3. (a) Use the Euclidean Algorithm to find values for s and t so that 97 s + 91 t = 1. 97 = 1*(91) + 6, then 91 = 15*(6) + 1 then back substition: 1 = 91 - 15*(6) = 91 - 15*( 97 - 91 ) = 16*(91) - 15*(97) watch your minus signs and distributive law. (b) Solve 91 x == 1 (mod 97). Then answer is the coefficient of 91 in 1 = 16*(91) - 15 *(97) (c) Suppose that p and q are numbers less than 97*91 such that <94,4) is equal to < p mod 97, p mod 91> and similarly <5,0> for q. If r is p+q, what is the representation of r? Well just <94+5,4+0> which is the same as <2,4> (d) What is the value of q? (Hint: You can use the Chinese Remainder theorem technique or get an expression for q in terms of 91 and then consider 97. Part (b) might be useful). q is <5,0> means that q==5 (mod 97) and q==0 (mod 91). This means that q = 91*x for some x. Any x would satisfy q==0(mod 91) so we just have to worry about q = 91*x == 5 (mod 97). We know the inverse of 91 mod 97 is 16 so we just multiply both sides by 16. 4. Find the smallest integer k such that n^2 - n log(n^5) is O(n^k) and provide detailed justifications for your answer (both directions, i.e. j works and j-1 does not). To prove that j = 2 works, we have to realize that log(n^5) = 5 * log(n) Then both n^2 and -n log (n^5) are O(n^2), hence by a theorem in the book we get that the sum is O(n^2). Now to prove that n^2 - n log(n^5) is not O(n). Suppose there is a C and a k so that n^2 - n log(n^5) < C n for all n > k (cancel n) we get n - log(n^5) < C or n < C + 5*log(n) for all n > k. Maybe the quickest way to finish is to say that this last expression clearly implies that n is O(log(n)) which we know is false. Hence there is no C and k as above, thus j=1 doesn't work. 5. Given a list a\_1, ..., a\_n considered as a function f(i)=a\_i this procedure computes (in words) the sum of i*x^i over those i such that f(i)=x. As usual discuss its worst case big-O complexity in terms of n. For definiteness count the number of times y is used in an operation. Procedure SUM(x,a\_1,...,a\_n) S:=0 for i:= 1 to n begin if x=a\_i then begin for k:=1 to i begin y:=1 for j:= 1 to i y:= y*x S:= S + y end end Ok outer loop goes 1 to n, Worst case is x keeps equalling a\_i so we do the inner loop. Fix an i in which x=a\_i we get a k which is going from 1 to i and for each such k let's see what happens: well we use y once (y:=1) and then we start a j loop in which j goes from 1 to i and each time we use y again. So that's i uses of j. Thus, for each k, we use y i+1 times. For each i, there are i values for k, so we use y i*(i+1) times during that loop of i. Worst case is that i takes on each value from 1 to n, so we get i=1 + i=2 + i=3 + ... + i=n 1*(1+1) + 2*(2+1) + 3*(3+1) + ... + n*(n+1) Each of these terms is less than n*n+1, so we get that this is n*(n+1) + ... + n*(n+1) = n* ( n*(n+1) ) which is O(n^3). Alan Dow Wed Oct 16 10:33:20 EDT 1996

Wed Oct 16 12:49:01 EDT 1996