=========================preview======================
(COMP170)[2011](s)midterm2~2630^_46481.pdf
Back to COMP170 Login to download
======================================================
HKUST C Department of Computer Science and Engineering
COMP170: Discrete Math Tools for CS C Spring 2011
Midterm Examination 2

Solution Key

Name: Student ID:
Email: Lecture and Tutorial:

Instructions
.
This is a closed book exam. It consists of 14 pages and 7 questions.

.
Please write your name, student ID, email, lecture section and tutorial on this page.

.
Please sign the honor code statement on page 2.

.
Answer all the questions within the space provided on the examination paper. You may use the back of the pages for your rough work. The last three pages are scrap paper and may also be used for rough work. Each question is on a separate page. This is for clarity and is not meant to imply that each question requires a full page answer. Many can be answered using only a few lines.

.
Unless otherwise speci.ed you must always explain how you de-rived your answer. A number without an explanation will be considered an incorrect answer.


Questions 1 2 3 4 5 6 7 Total
Points 16 17 18 18 9 10 12
Score

As part of HKUSTs introduction of an honor code, the HKUST Senate has recommended that all students be asked to sign a brief declaration printed on examination answer books that their answers are their own work, and that they are aware of the regulations relating to academic integrity. Following this, please read and sign the declaration below.
I declare that the answers submitted for this examination are my own work.
I understand that sanctions will be imposed, if I am found to have violated the University regulations governing academic integrity.
Students Name:

Students Signature:
Problem 1 [16 pts] Evaluate the following expressions and show your calculations.You must not use repeated squaring.
(a)
31081 mod 7.

(b)
18060 mod 61.

(c)
18360 mod 61.

(d)
1013 mod 26.


Solution:
(a)
31081 mod 7
3(6180+1) mod 7

= = (3 (36)180) mod 7 = ((3 mod 7)((36) mod 7)180) mod 7 = 3 mod 7 (by the fermats little theorem) =3
(b)
18060 mod 61 = (180 mod 61)60 mod 61 = 5860 mod 61 = 1 by the fermats little theorem.

(c)
18360 mod 61 = 0 since 183 is multiple of 61.

(d)
By Euclids division theorem, we have


r = 1013 mod 26 = 1013 . 26q = 2(5 1012 . 13q)
where 0 r< 26. This implies 0 2 r < 13 and thus r
=5 1012mod13 = 5
2
.
Therefore,

r = 10
Problem 2 [17 pts] Consider the following two sets of modular equations:
(a)


x mod20 = 1 x mod21 = 3
(b)

x mod15 = 1 x mod21 = 3
For each of the two sets of equations answer the following question:
Does there exist a solution for x Zmn, where m and n are the
divisors of the two modular equations?
Note: in (a), (m, n) = (20, 21); in (b), (m, n) = (15, 21).
For each set, explain why your answer is correct. Furthermore, if your an-swer is that there is a solution, give a solution.
Solution:
(a)
Since gcd(21, 20) = 1, th