```

Discrete Mathematics (Dow) -- Test 1 Version C

In all questions, clear reasoning must be provided.

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

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

Alan Dow
Wed Oct 16 12:45:38 EDT 1996