```
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
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)
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
```

Alan Dow
Wed Oct 16 12:49:01 EDT 1996