Question

( NO HAND WRITING PLEASE )

Q1: Suppose that a and b are integers, a ≡ 11 (mod 19), and

b ≡ 3 (mod 19). Find the integer c with 0 ≤ c ≤ 18 such

that

a) c ≡ 13a (mod 19).

b) c ≡ 8b (mod 19).

c) c ≡ a − b (mod 19).

d) c ≡ 7a + 3b (mod 19).

e) c ≡ 2a² + 3b² (mod 19).

Q2:

List all the steps used to search for 10 in the sequence 1,3, 4, 5, 6, 8, 9, 11 using

a) A linear search.

b) A binary search.

Answer 1

1) Given that a and b are integers such that a 11(mod 19) and b 3(mod 19) and c is an integer such that .

Now, a) We have, a 11(mod 19)

i.e., a = 19*m + 11, where m is an integer.

i.e., 13a = 13*(19*m + 11)

i.e., 13a = 19*(13*m) + 143

i.e., 13a = 19*(13*m + 7) + 10

i.e., 13a = 19*m' + 10 [where m' = 13*m + 7]

Given, c 13a(mod 19)

i.e., c = 19*k + 13a, where k is an integer

i.e., c = 19*k + 19*m' + 10

i.e., c = 19*(k + m') + 10 [where m' = 13*m + 7]

i.e., c = 19*k' + 10 [where k' = k + m']

Since, c is an integer such that and k' is an integer.

Therefore, c = 10 [putting k' = 0]

b) We have, b 3(mod 19)

i.e., b = 19*n + 3

i.e., 8b = 8*(19*n + 3)

i.e., 8b = 19*(8*n) + 24

i.e., 8b = 19*(8*n + 1) + 5

Given, c 8b(mod 19)

i.e., c = 19*k + 8b, where k is an integer

i.e., c = 19*k + 19*(8*n + 1) + 5

i.e., c = 19*(k + 8*n + 1) + 5

i.e., c = 19*k' + 5 [where k' = k + 8*n + 1]

Since, c is an integer such that and k' is an integer.

Therefore, c = 5 [putting k' = 0]

c)We have, c a-b(mod 19)

i.e., c = 19*k + (19*m + 11) + (19*n + 3)

i.e., c = 19*(k+m+n) + 14

i.e., c = 19*k' + 14 [where k' = k+m+n]

Since, c is an integer such that and k' is an integer.

Therefore, c = 14 [putting k' = 0]

d) We have, c 7a+3b(mod 19)

i.e., c = 19*k + 7*(19*m + 11) + 3*(19*n + 3)

i.e., c = 19*k + 19*(7*m + 3*n) + 77 + 9

i.e., c = 19*(k + 7*m + 3*n) + 86

i.e., c = 19*(k + 7*m + 3*n + 4) + 10

i.e., c = 19*k' + 10 [where k' = k + 7*m + 3*n + 4]

Since, c is an integer such that and k' is an integer.

Therefore, c = 10 [putting k' = 0]

e) We have, c 2a²+3b²(mod 19)

i.e., c = 19*k + 2*(19*m + 11)² + 3*(19*n + 3)²

i.e., c = 19*k + 2*[19*(19*m² + 22*m) + 121] + 3*[19*(19*n² + 6*n) + 9]

i.e., c = 19*[k + 2*(19*m² + 22*m) + 3*(19*n² + 6*n)] + 242 + 27

i.e., c = 19*[k + 2*(19*m² + 22*m) + 3*(19*n² + 6*n)] + 269

i.e., c = 19*[k + 2*(19*m² + 22*m) + 3*(19*n² + 6*n) + 14] + 3

i.e., c = 19*k' + 3 [where k' = k + 2*(19*m² + 22*m) + 3*(19*n² + 6*n) + 14]

Since, c is an integer such that and k' is an integer.

Therefore, c = 3 [putting k' = 0]