Back to Subject

Unit 3: Number Theory-III - Practice Quiz

MTH381 — Number Theory And Cryptography 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 A linear congruence is an equation of the form:

linear congruences Easy
A. where the modulus itself changes at every step of the solving process
B.
C.
D.

2 The linear congruence has a solution if and only if:

linear congruences Easy
A. divides
B. divides
C. always
D. divides

3 An inverse of modulo is an integer such that:

linear congruences Easy
A.
B.
C.
D.

4 An inverse of modulo exists if and only if:

linear congruences Easy
A. is even
B.
C.
D. is prime

5 How many incongruent solutions modulo does have when and ?

linear congruences Easy
A.
B.
C.
D.

6 The Chinese Remainder Theorem guarantees a unique solution modulo when the moduli are:

The Chinese remainder theorem Easy
A. pairwise relatively prime
B. all even
C. all prime
D. all equal

7 For the system and , the unique solution modulo is:

The Chinese remainder theorem Easy
A.
B.
C.
D.

8 In the CRT, the value used in the construction of the solution equals:

The Chinese remainder theorem Easy
A.
B.
C.
D.

9 The Chinese Remainder Theorem is primarily used to solve:

The Chinese remainder theorem Easy
A. a differential equation
B. a single quadratic equation
C. a system of linear inequalities
D. a system of simultaneous linear congruences

10 In the CRT construction, is defined as:

The Chinese remainder theorem Easy
A.
B.
C.
D.

11 Representing a large integer by its residues modulo pairwise relatively prime moduli is useful because:

computer arithmetic with large integers Easy
A. it removes the need for any modulus
B. arithmetic can be done independently and in parallel on each component
C. it converts the number to binary automatically
D. it always reduces the number to a single digit

12 In computer arithmetic, representing large integers by residues modulo a set of moduli relies on which theorem for uniqueness?

computer arithmetic with large integers Easy
A. The Chinese Remainder Theorem
B. Wilson's Theorem
C. The Binomial Theorem
D. Fermat's Little Theorem

13 A key advantage of modular (residue) arithmetic for large numbers on computers is that it:

computer arithmetic with large integers Easy
A. eliminates the need for storing the moduli
B. avoids carries propagating across the whole number during addition and multiplication of the smaller residue components
C. only works for negative integers
D. requires floating-point hardware

14 If moduli are pairwise relatively prime, a residue representation uniquely represents integers in the range:

computer arithmetic with large integers Easy
A. to
B. to
C. to
D. to

15 Fermat's Little Theorem states that if is prime and , then:

Fermat's little theorem Easy
A.
B.
C.
D.

16 An equivalent form of Fermat's Little Theorem, valid for any integer and prime , is:

Fermat's little theorem Easy
A.
B.
C.
D.

17 Using Fermat's Little Theorem, what is ?

Fermat's little theorem Easy
A.
B.
C.
D.

18 Fermat's Little Theorem requires that the modulus be:

Fermat's little theorem Easy
A. a prime number
B. an even number
C. a perfect square
D. a composite number

19 A common application of congruences in computer science is:

applications of congruences Easy
A. sorting a list in ascending order
B. hashing functions that map keys using
C. drawing graphs of polynomials
D. computing derivatives of functions

20 Check digit schemes, such as those used in ISBNs and credit card numbers, are examples of applications of:

applications of congruences Easy
A. graph coloring
B. numerical integration
C. congruences
D. matrix inversion

21 Find the solution to the linear congruence .

linear congruences Medium
A.
B.
C.
D.

22 How many incongruent solutions modulo does have?

linear congruences Medium
A.
B.
C. No solutions
D.

23 For which value of does the congruence have no solution?

linear congruences Medium
A.
B.
C.
D.

24 What is the multiplicative inverse of modulo ?

linear congruences Medium
A.
B.
C.
D.

25 Find the smallest positive integer satisfying , , and .

The Chinese remainder theorem Medium
A.
B.
C.
D.

26 The system and is solved. Which statement is correct?

The Chinese remainder theorem Medium
A. The unique solution modulo is
B. The solution is
C. No solution exists at all
D. No solution exists because does not divide ... actually it does, so solutions exist modulo

27 In the Chinese Remainder Theorem, for moduli to guarantee a unique solution modulo , the moduli must be:

The Chinese remainder theorem Medium
A. All even
B. In increasing order
C. Pairwise coprime
D. All prime numbers

28 Solve and for the least positive .

The Chinese remainder theorem Medium
A.
B.
C.
D.

29 To compute efficiently, which technique is most appropriate?

computer arithmetic with large integers Medium
A. Computing fully then dividing
B. Newton's method for roots
C. Fast (modular) exponentiation by repeated squaring
D. Long division of decimal digits

30 Using CRT-based representation, an integer can be uniquely represented by its residues modulo which pair of moduli?

computer arithmetic with large integers Medium
A. and
B. and
C. and
D. and

31 What is the value of , useful for tracking least significant digits in large integer arithmetic?

computer arithmetic with large integers Medium
A.
B.
C.
D.

32 In the repeated squaring method to compute , the exponent is processed using its representation in which base?

computer arithmetic with large integers Medium
A. Base
B. Decimal (base 10)
C. Hexadecimal (base 16)
D. Binary (base 2)

33 Using Fermat's Little Theorem, compute .

Fermat's little theorem Medium
A.
B.
C.
D.

34 Fermat's Little Theorem states that if is prime and , then which congruence holds?

Fermat's little theorem Medium
A.
B.
C.
D.

35 What is ?

Fermat's little theorem Medium
A.
B.
C.
D.

36 Compute using Fermat's Little Theorem.

Fermat's little theorem Medium
A.
B.
C.
D.

37 In a hashing function , at which slot is the key stored?

applications of congruences Medium
A.
B.
C.
D.

38 A pseudorandom number generator uses with seed . What is ?

applications of congruences Medium
A.
B.
C.
D.

39 The check digit of an ISBN-10 is chosen so that . This is a direct application of which concept?

applications of congruences Medium
A. Continued fractions used to encode data
B. Congruences used to detect errors
C. Modular exponentiation used to sign messages
D. Prime factorization used to compress digits

40 Today is Thursday. Using congruences modulo to model days of the week, what day will it be after days?

applications of congruences Medium
A. Saturday
B. Sunday
C. Monday
D. Friday

41 How many incongruent solutions does the congruence have?

linear congruences Hard
A. 0
B. 1
C. 3
D. 6

42 Find the unique solution modulo of .

linear congruences Hard
A.
B.
C.
D.

43 For the congruence to be solvable, the constant must be:

linear congruences Hard
A. coprime to
B. a multiple of
C. a multiple of
D. a multiple of

44 Find the smallest positive integer satisfying , , and .

The Chinese remainder theorem Hard
A. 58
B. 17
C. 23
D. 52

45 Solve the system , , .

The Chinese remainder theorem Hard
A.
B.
C.
D.

46 Which of the following systems has no solution?

The Chinese remainder theorem Hard
A.
B.
C.
D.

47 Solve and .

The Chinese remainder theorem Hard
A.
B.
C.
D.

48 Compute .

Fermat's little theorem Hard
A. 4
B. 1
C. 2
D. 5

49 Compute .

Fermat's little theorem Hard
A. 2
B. 16
C. 8
D. 1

50 Using Fermat's little theorem, the multiplicative inverse of modulo the prime equals:

Fermat's little theorem Hard
A. 8
B. 9
C. 5
D. 3

51 The value of (where ) is:

Fermat's little theorem Hard
A. 1
B. 2
C. 170
D. 0

52 Which of the following is a Carmichael number?

applications of congruences Hard
A. 563
B. 561
C. 533
D. 571

53 How many incongruent solutions does have?

applications of congruences Hard
A. 1
B. 8
C. 2
D. 4

54 Compute .

Fermat's little theorem Hard
A. 3
B. 9
C. 7
D. 5

55 Multiplying two -digit integers using the Karatsuba algorithm has time complexity:

computer arithmetic with large integers Hard
A.
B.
C.
D.

56 Computing by fast modular exponentiation (repeated squaring) uses how many modular multiplications?

computer arithmetic with large integers Hard
A.
B.
C.
D.

57 How many -bit words are needed to store an unsigned -bit integer?

computer arithmetic with large integers Hard
A. 16
B. 32
C. 128
D. 64

58 The smallest positive solution of is:

linear congruences Hard
A. 3
B. 2
C. 9
D. 4

59 Using CRT with , the value of is:

The Chinese remainder theorem Hard
A. 64
B. 12
C. 23
D. 1

60 The Fermat primality test declares 'probably prime' to base but composite to base . What property explains why the base- test fails?

applications of congruences Hard
A. is a perfect square, invalidating the test
B. is a Fermat pseudoprime to base since
C. is prime and the test is inconsistent
D. is coprime to but not to
Previous MCQ
Unit 2
Next MCQ
Unit 4