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