If x a mod n = c and x b mod n = d then x a+b mod equals A. c + d mod n B. c*d m

ID: 3825483 • Letter: I

Question

If xa mod n = c and xb mod n = d then xa+b mod equals

A. c + d mod n

B. c*d mod n

C. cd mod n

D. None of the above

If c = x mod n then c is guaranteed to be in which of the following sets

A: { 1, 2, 3, … n-1 }

B: { 0, 1, 2, 3, …. n-1 }

C: { -(n-1), -(n-2), -(n-3), … -2, -1 0 }

D: { 1, 2, 3, …. n }

Which of the following statement(s) are true.

a: P is contained in NP. b: All solvable problems are in P.

c: The traveling salesman problem is in NP. d:The traveling salesman problem is not solvable.

----------------------------------------------------------------------------------------------------------------------------------------------------

A: a b c

B: a c

C: a c d

D: a, d

Answer:-

1) A

c + d mod n

as, xa mod n = c

means c-xa is equals to some integral multiple of n. In the same way

xb mod n = d

means d-xb is equals to some integral multiple of n.By solving these two equations we get the answer.

2) D

{ 1, 2, 3, …. n }

3) A

a,b,c

a: P is contained in NP.

b: All solvable problems are in P.

c: The traveling salesman problem is in NP.

P is subset of NP. Each problem in P is a problem in NP.

The traveling salesman problem is a NP complete so it is in NP and it completes in polynomial time so it can be solvable.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.