StudyFox
कीमतेंब्लॉगएक्सटेंशनमुफ़्त टूल
  • कीमतें
  • ब्लॉग
  • एक्सटेंशन
  • मुफ़्त टूल
  • शुरू करेंसाइन इन
StudyFox

अपने नोट्स, PDF और स्लाइड्स को फ़्लैशकार्ड, क्विज़, नोट्स और माइंड मैप में बदलें।

StudyFox खोलें

स्टडी टूल्स

  • होमवर्क हेल्पर
  • नोट मेकर
  • फ़्लैशकार्ड मेकर
  • क्विज़ मेकर
  • माइंड मैप मेकर

प्रोडक्ट

  • कीमतें
  • Chrome एक्सटेंशन
  • मुफ़्त एक्सटेंशन
  • स्टडी सेट देखें
  • ब्लॉग

सहायता

  • सहायता केंद्र
  • संपर्क करें
  • गोपनीयता नीति
  • सेवा की शर्तें

तुलना करें

  • Chegg का विकल्प
  • Course Hero का विकल्प
  • Coursology का विकल्प
  • Photomath का विकल्प
  • Gauthmath का विकल्प
  • PhotoSolve का विकल्प
  • CollegeTools का विकल्प
  • Transcript का विकल्प
  • SmartSolve का विकल्प
  • Homeworkify का विकल्प
  • AnswersAi का विकल्प
  • StudyX का विकल्प
  • Quizlet का विकल्प
  • Anki का विकल्प
  • Knowt का विकल्प
  • Brainscape का विकल्प
  • सभी तुलनाएँ

© 2026 StudyFox AI. सर्वाधिकार सुरक्षित।

  • X
  • Discord
  • Instagram
ExploreMathDiscrete MathDiscrete Math Quiz: Number Theory and Modular Arithmetic

Quiz · Medium

Discrete Math Quiz: Number Theory and Modular Arithmetic

Twenty questions on gcd and the Euclidean algorithm, primes, congruences, modular inverses, Fermat, Euler, the Chinese remainder theorem and RSA.

by Kill h.20 questionsCreated Nov 20, 2026, 08:28 PM
Discrete Math· Number TheoryTags#number-theory#modular-arithmetic#gcd#rsa

20 questions

  1. 1

    What is ?

    • 42

    • B

      6

    • C

      21

    • D

      252

    84 = 2^2 * 3 * 7 and 126 = 2 * 3^2 * 7, so gcd = 2 * 3 * 7 = 42. (252 is the lcm.)

  2. 2

    Using the Euclidean algorithm, equals

    • A

      7

    • B

      33

    • C

      147

    • 21

    1071 = 2*462 + 147; 462 = 3*147 + 21; 147 = 7*21. The last non-zero remainder is 21.

  3. 3

    How many positive divisors does 72 have?

    • A

      8

    • 12

    • C

      10

    • D

      24

    72 = 2^3 * 3^2, so (3 + 1)(2 + 1) = 12.

  4. 4

    Which of these numbers is prime?

    • A

      91

    • B

      119

    • 149

    • D

      143

    91 = 7*13, 119 = 7*17, 143 = 11*13. 149 has no prime factor up to 12 (not 2, 3, 5, 7, 11), so it is prime.

  5. 5

    The remainder of divided by 7 is

    • A

      1

    • B

      4

    • 2

    • D

      6

    2^3 = 8 = 1 (mod 7), so 2^100 = 2^(99+1) = (2^3)^33 * 2 = 2.

  6. 6

    The inverse of 4 modulo 9 is

    • 7

    • B

      2

    • C

      5

    • D

      8

    4 * 7 = 28 = 3 * 9 + 1, so the inverse is 7. 4 * 5 = 20 = 2 (mod 9) is not 1.

  7. 7

    How many solutions modulo 12 does have?

    • A

      0

    • 4

    • C

      1

    • D

      2

    gcd(8, 12) = 4 divides 4, so there are 4 solutions mod 12 (x = 2, 5, 8, 11).

  8. 8

    The number is

    • A

      12

    • B

      36

    • C

      44

    • 24

    45 = 3^2 * 5, so phi = 45 * (2/3) * (4/5) = 24.

  9. 9

    Which statement is Fermat's little theorem (p prime, p does not divide a)?

    • A

    • B

    • C

    Fermat gives a^(p-1) = 1. a^p = a (not 1) holds for all a, and Wilson's theorem says (p-1)! = -1.

  10. 10

    The Chinese remainder theorem guarantees a unique solution mod when

    • A

      m1 and m2 are both prime

    • m1 and m2 are coprime

    • C

      m1 divides m2

    • D

      m1 + m2 is even

    Pairwise coprime moduli are what is required; they need not be prime (e.g. 4 and 9).

  11. 11

    Which has no solution?

    • A

    • B

    • D

    gcd(6, 9) = 3 does not divide 4, so 6x = 4 (mod 9) is unsolvable. The others have gcd 1 or gcd dividing the right side.

  12. 12

    The smallest positive x with and is

    • 17

    • B

      7

    • C

      9

    • D

      21

    Candidates congruent to 2 mod 5: 2, 7, 12, 17; the first that is 1 mod 4 is 17 (7 = 3 mod 4, 12 = 0 mod 4, 17 = 1 mod 4).

  13. 13

    In RSA with p = 5, q = 11 and e = 3, the private exponent d is

    • A

      7

    • B

      13

    • 27

    • D

      17

    phi = 4 * 10 = 40. We need 3d = 1 (mod 40): d = 27 since 81 = 2*40 + 1. (7 would give 21, not 1 mod 40.)

  14. 14

    Why is the Sieve of Eratosthenes on the grid up to 120 only run with the primes 2, 3, 5, 7?

    • A

      Larger primes have no multiples in the grid

    • B

      Multiples of 11 are already prime

    • C

      Only odd numbers need sieving

    • Every composite up to 120 has a prime factor at most 10

    A composite n has a prime factor at most sqrt(n), and sqrt(120) is about 10.95. Multiples of 11 below 121 (22, 33, ...) already have a smaller prime factor. Image: Ricordisamoa, public domain, via Wikimedia Commons.

  15. 15

    The 21 x 15 rectangle in the picture is tiled by squares as in the Euclidean algorithm. What is ?

    • 3

    • B

      5

    • C

      6

    • D

      15

    The last (smallest) squares have side 3, so gcd(21, 15) = 3. Image: Kelam, CC BY-SA 3.0, via Wikimedia Commons.

  16. 16

    True or false: for positive integers a and b.

    • True

    • B

      False

    Taking, for each prime, the min and max exponents multiplies to the sum of exponents, which is exactly ab.

  17. 17

    What day of the week is it 1000 days after a Monday?

    • A

      Tuesday

    • Sunday

    • C

      Wednesday

    • D

      Friday

    1000 = 142 * 7 + 6, so the day moves forward 6 places: Monday + 6 days = Sunday. Only the remainder mod 7 matters.

  18. 18

    The last two digits of are (use )

    • A

      03

    • B

      09

    • 01

    • D

      81

    3^20 = 1 (mod 100), so 3^100 = (3^20)^5 = 1 (mod 100). Euler's theorem gives only 3^40 = 1, but 20 is the actual order.

  19. 19

    Which statement about primes is correct?

    • A

      There are finitely many twin primes

    • There are infinitely many primes

    • C

      Every even integer greater than 2 is a sum of two primes (proved)

    • D

      Every prime is odd

    Euclid's theorem. The Goldbach and twin prime statements are conjectures, and 2 is an even prime.

  20. 20

    For prime p = 13, what is by Wilson's theorem?

    • 12

    • B

      1

    • C

      6

    • D

      0

    (p-1)! = -1 (mod p), and -1 = 12 (mod 13).