250+ TOP MCQs on Number Theory and Answers

Cryptography Multiple Choice Questions on “Number Theory”.

1. What is the Discrete logarithm to the base 10 (mod 19) for a =7?
a) 12
b) 14
c) 8
d) 11

Answer: a
Clarification: log_10(7) mod 19 = 12.

2. 3²⁰¹ mod 11 =
a) 3
b) 5
c) 6
d) 10

Answer: a
Clarification: Use Fermats Theorum. Fermat’s Theorem states that if p is prime and a is a positive integer not divisible
by p, then a^(p–1) = 1 (mod p). Therefore 3¹⁰ = 1 (mod 11). Therefore
3^201 = (3¹⁰)²⁰ x 3 = 3 (mod 11).

3. Find a number x between 0 and 28 with x^85 congruent to 6 mod 29.
a) 22
b) 12
c) 6
d) 18

Answer: c
Clarification: Use Fermats Theorum.

4. What is the Discrete logarithm to the base 13 (mod 19) for a =13?
a) 14
b) 1
c) 8
d) 17

Answer: b
Clarification: log_13(13) mod 19 = 1.

5. What is the Discrete logarithm to the base 15 (mod 19) for a =9?
a) 3
b) 7
c) 12
d) 4

Answer: d
Clarification: log_15(9) mod 19 = 4.

6. Find a number x between 0 and 28 with x⁸⁵ congruent to 6 mod 35.
a) 6
b) 32
c) 8
d) 28

Answer: a
Clarification: Use Eulers Theorum.

7. Find a number ‘a’ between 0 and 72 with ‘a’ congruent to 9794 mod 73.
a) 53
b) 29
c) 12
d) 37

Answer: c
Clarification: Use Fermats Theorum.

8. What is the Discrete logarithm to the base 2 (mod 19) for a =7?
a) 3
b) 4
c) 6
d) 9

Answer: c
Clarification: log_2(7) mod 19 = 6.

9. ᶲ(41)=
a) 40
b) 20
c) 18
d) 22

Answer: a
Clarification: 41 is a prime.

10. ᶲ(27)=
a) 6
b) 12
c) 26
d) 18

Answer: d
Clarification: ᶲ(27) = ᶲ(33) = 3³ – 3² = 27 – 9 = 18.

11. Find a number ‘a’ between 0 and 9 such that ‘a’ is congruent to 7^1000 mod 10.
a) 2
b) 1
c) 3
d) 4

Answer: b
Clarification: Use Eulers Theorum.

12. ᶲ(440)=
a) 200
b) 180
c) 160
d) 220

Answer: c
Clarification: ᶲ(440) = ᶲ(2^3) x ᶲ(5) x ᶲ(11) = (2^3 – 2^2) x 4 x 10 = 160.

13. GCD(n,n+1) = 1 always.
a) True
b) False

Answer: a
Clarification: If p were any prime dividing n and n + 1 it would also have to divide (n + 1) – n = 1. Thus GCD of 2 consecutive numbers is always 1.