Discrete Math Quiz: Modular Arithmetic
12 questions · exam conditions
0:00
Modular ArithmeticQuestion 1 of 12

What is the smallest positive integer nn such that 2n≡1(mod35)2^n \equiv 1 \pmod{35}?

6
12
24
30
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Modular Arithmetic

Practice Modular Arithmetic in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Modular Arithmetic, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

What is the smallest positive integer nn such that 2n≡1(mod35)2^n \equiv 1 \pmod{35}?

  1. 6
  2. 12 (correct answer)
  3. 24
  4. 30
Explanation: Since 35=5⋅735 = 5 \cdot 7 and gcd⁡(5,7)=1\gcd(5,7) = 1, we use the Chinese Remainder Theorem. We need 2n≡1(mod5)2^n \equiv 1 \pmod{5} and 2n≡1(mod7)2^n \equiv 1 \pmod{7} simultaneously. For  mod 5\bmod 5: 21≡22^1 \equiv 2, 22≡42^2 \equiv 4, 23≡32^3 \equiv 3, 24≡1(mod5)2^4 \equiv 1 \pmod{5}. So the order of 22 modulo 55 is 44. For  mod 7\bmod 7: 21≡22^1 \equiv 2, 22≡42^2 \equiv 4, 23≡1(mod7)2^3 \equiv 1 \pmod{7}. So the order of 22 modulo 77 is 33. The smallest nn such that 2n≡12^n \equiv 1 modulo both 55 and 77 is lcm(4,3)=12\text{lcm}(4,3) = 12. Choice A (6) is 4+3−14 + 3 - 1, a common error when adding orders instead of taking the LCM. Choice C (24) is 4×3×24 \times 3 \times 2, possibly from incorrectly computing lcm(4,3)×2\text{lcm}(4,3) \times 2. Choice D (30) might come from using ϕ(35)=ϕ(5)ϕ(7)=4⋅6=24\phi(35) = \phi(5)\phi(7) = 4 \cdot 6 = 24, then adding 6.

Question 2

Find the remainder when 31003^{100} is divided by 7.

  1. 1
  2. 2
  3. 4 (correct answer)
  4. 6
Explanation: We use Fermat's Little Theorem. Since 7 is prime and gcd⁡(3,7)=1\gcd(3,7) = 1, we have 36≡1(mod7)3^{6} \equiv 1 \pmod{7}. Now 100=6⋅16+4100 = 6 \cdot 16 + 4, so 3100=36⋅16+4=(36)16⋅34≡116⋅34≡34(mod7)3^{100} = 3^{6 \cdot 16 + 4} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 \equiv 3^4 \pmod{7}. Computing 34=81=11⋅7+43^4 = 81 = 11 \cdot 7 + 4, so 34≡4(mod7)3^4 \equiv 4 \pmod{7}. Choice A (1) would result from incorrectly thinking 3100≡3100 mod 6=34≡13^{100} \equiv 3^{100 \bmod 6} = 3^4 \equiv 1. Choice B (2) might come from computing 32=9≡2(mod7)3^2 = 9 \equiv 2 \pmod{7} and stopping there. Choice D (6) could result from computing 36≡13^6 \equiv 1, then incorrectly getting 3100≡3100−6=394≡31⋅393≡63^{100} \equiv 3^{100-6} = 3^{94} \equiv 3^1 \cdot 3^{93} \equiv 6.

Question 3

If x≡4(mod15)x \equiv 4 \pmod{15} and y≡11(mod15)y \equiv 11 \pmod{15}, what is the smallest positive value of x2+y2x^2 + y^2?

  1. 137 (correct answer)
  2. 152
  3. 167
  4. 182
Explanation: We have x=15k+4x = 15k + 4 and y=15j+11y = 15j + 11 for integers k,j≥0k, j \geq 0. Then x2+y2=(15k+4)2+(15j+11)2=225k2+120k+16+225j2+330j+121=225(k2+j2)+120k+330j+137x^2 + y^2 = (15k + 4)^2 + (15j + 11)^2 = 225k^2 + 120k + 16 + 225j^2 + 330j + 121 = 225(k^2 + j^2) + 120k + 330j + 137. To minimize this, we want to minimize 225(k2+j2)+120k+330j225(k^2 + j^2) + 120k + 330j. Since all coefficients are positive and k,j≥0k, j \geq 0, the minimum occurs at k=j=0k = j = 0. This gives x2+y2=42+112=16+121=137x^2 + y^2 = 4^2 + 11^2 = 16 + 121 = 137. Choice B might result from using x=4,y=11x = 4, y = 11 but adding an extra term. Choice C could come from x=19,y=11x = 19, y = 11: 192+112=361+121=48219^2 + 11^2 = 361 + 121 = 482, which doesn't match. Choice D similarly doesn't align with small values.

Question 4

Let pp be a prime number greater than 3. If p2≡1(mod24)p^2 \equiv 1 \pmod{24}, what is the remainder when p3p^3 is divided by 24?

  1. 1
  2. 5 (correct answer)
  3. 11
  4. 23
Explanation: Since pp is prime and p>3p > 3, we have gcd⁡(p,6)=1\gcd(p, 6) = 1. Also, pp is odd, so p2p^2 is odd. For p2≡1(mod24)p^2 \equiv 1 \pmod{24}, we need p2≡1(mod8)p^2 \equiv 1 \pmod{8} and p2≡1(mod3)p^2 \equiv 1 \pmod{3}. Since pp is odd, p=2k+1p = 2k+1 for some kk, so p2=4k2+4k+1=4k(k+1)+1p^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1. Since either kk or k+1k+1 is even, k(k+1)k(k+1) is even, so 4k(k+1)≡0(mod8)4k(k+1) \equiv 0 \pmod{8}. Thus p2≡1(mod8)p^2 \equiv 1 \pmod{8} for any odd pp. For p2≡1(mod3)p^2 \equiv 1 \pmod{3}, we need p≢0(mod3)p \not\equiv 0 \pmod{3}. Since p>3p > 3 is prime, this is satisfied. By Fermat's Little Theorem, p2≡1(mod3)p^2 \equiv 1 \pmod{3} when p≡±1(mod3)p \equiv \pm 1 \pmod{3}. So the condition p2≡1(mod24)p^2 \equiv 1 \pmod{24} is satisfied by primes p>3p > 3 with p≡±1(mod3)p \equiv \pm 1 \pmod{3}, which includes p≡1,5(mod6)p \equiv 1, 5 \pmod{6} (since pp must be coprime to 6). Now, p3=p⋅p2≡p⋅1=p(mod24)p^3 = p \cdot p^2 \equiv p \cdot 1 = p \pmod{24}. Since pp is a prime greater than 3, the possible values modulo 24 are those coprime to 24. We have gcd⁡(n,24)=1\gcd(n, 24) = 1 when n≡1,5,7,11,13,17,19,23(mod24)n \equiv 1, 5, 7, 11, 13, 17, 19, 23 \pmod{24}. Among the primes, we could have p=5p = 5, giving p3≡5(mod24)p^3 \equiv 5 \pmod{24}. Let's verify: 52=25≡1(mod24)5^2 = 25 \equiv 1 \pmod{24} ✓. So p3≡5(mod24)p^3 \equiv 5 \pmod{24}. Choice A assumes p3≡(p2)⋅p−1≡1(mod24)p^3 \equiv (p^2) \cdot p^{-1} \equiv 1 \pmod{24}. Choice C might come from p=11p = 11, but 112=121≢1(mod24)11^2 = 121 \not\equiv 1 \pmod{24}. Choice D might assume p≡−1(mod24)p \equiv -1 \pmod{24}.

Question 5

If n≡4(mod9)n \equiv 4 \pmod{9} and n2≡r(mod9)n^2 \equiv r \pmod{9}, what is the value of rr?

  1. 1
  2. 4
  3. 7 (correct answer)
  4. 8
Explanation: Since n≡4(mod9)n \equiv 4 \pmod{9}, we have n2≡42≡16(mod9)n^2 \equiv 4^2 \equiv 16 \pmod{9}. Now 16=9+716 = 9 + 7, so 16≡7(mod9)16 \equiv 7 \pmod{9}. Therefore r=7r = 7. Choice A results from incorrectly computing 42−154^2 - 15. Choice B assumes n2≡n(mod9)n^2 \equiv n \pmod{9}. Choice D comes from computing 16−8=816 - 8 = 8 instead of the proper modular reduction.

Question 6

What is the last two digits of 31003^{100}?

  1. 01 (correct answer)
  2. 49
  3. 51
  4. 81
Explanation: We need 3100(mod100)3^{100} \pmod{100}. Using Euler's theorem, ϕ(100)=ϕ(4)⋅ϕ(25)=2⋅20=40\phi(100) = \phi(4) \cdot \phi(25) = 2 \cdot 20 = 40. Since gcd⁡(3,100)=1\gcd(3, 100) = 1, we have 340≡1(mod100)3^{40} \equiv 1 \pmod{100}. Therefore 3100=340⋅2+20=(340)2⋅320≡12⋅320≡320(mod100)3^{100} = 3^{40 \cdot 2 + 20} = (3^{40})^2 \cdot 3^{20} \equiv 1^2 \cdot 3^{20} \equiv 3^{20} \pmod{100}. Computing 3203^{20}: 310=59049≡49(mod100)3^{10} = 59049 \equiv 49 \pmod{100}, so 320≡492=2401≡1(mod100)3^{20} \equiv 49^2 = 2401 \equiv 1 \pmod{100}. Choice B is 310(mod100)3^{10} \pmod{100}. Choice C results from incorrect exponent arithmetic. Choice D assumes 34=813^4 = 81 pattern repeats incorrectly.

Question 7

If a≡13(mod17)a \equiv 13 \pmod{17} and b≡8(mod17)b \equiv 8 \pmod{17}, what is (a−2b)2(mod17)(a - 2b)^2 \pmod{17}?

  1. 4
  2. 9 (correct answer)
  3. 12
  4. 16
Explanation: First, compute a−2b≡13−2(8)≡13−16≡−3≡14(mod17)a - 2b \equiv 13 - 2(8) \equiv 13 - 16 \equiv -3 \equiv 14 \pmod{17}. Then (a−2b)2≡142≡196(mod17)(a - 2b)^2 \equiv 14^2 \equiv 196 \pmod{17}. Since 196=11⋅17+9196 = 11 \cdot 17 + 9, we have 196≡9(mod17)196 \equiv 9 \pmod{17}. Choice A results from computing (−3)2=9(-3)^2 = 9 but then incorrectly reducing 9−59 - 5. Choice C comes from computing 13−1=1213 - 1 = 12 incorrectly. Choice D assumes (14)2≡(−3)2≡16(14)^2 \equiv (-3)^2 \equiv 16 by forgetting the modular reduction.

Question 8

Find the number of solutions to 6x≡9(mod15)6x \equiv 9 \pmod{15} where 0≤x<150 \leq x < 15.

  1. 0
  2. 1
  3. 3 (correct answer)
  4. 5
Explanation: For ax≡b(modm)ax \equiv b \pmod{m} to have solutions, we need gcd⁡(a,m)∣b\gcd(a,m) | b. Here gcd⁡(6,15)=3\gcd(6,15) = 3 and 3∣93 | 9, so solutions exist. The number of solutions is gcd⁡(6,15)=3\gcd(6,15) = 3. To find them, we first solve 63x≡93(mod153)\frac{6}{3}x \equiv \frac{9}{3} \pmod{\frac{15}{3}}, which gives 2x≡3(mod5)2x \equiv 3 \pmod{5}. Since 2⋅3=6≡1(mod5)2 \cdot 3 = 6 \equiv 1 \pmod{5}, we have x≡3⋅3≡4(mod5)x \equiv 3 \cdot 3 \equiv 4 \pmod{5}. So x∈{4,9,14}x \in \{4, 9, 14\}. Choice A assumes no solutions exist. Choice B counts only one fundamental solution. Choice D incorrectly uses ϕ(15)=8\phi(15) = 8 somehow.

Question 9

If a≡7(mod13)a \equiv 7 \pmod{13} and b≡11(mod13)b \equiv 11 \pmod{13}, what is the smallest positive integer xx such that ax≡b(mod13)ax \equiv b \pmod{13}?

  1. 6
  2. 9 (correct answer)
  3. 11
  4. 12
Explanation: We need to solve 7x≡11(mod13)7x \equiv 11 \pmod{13}. First, we find the multiplicative inverse of 7 modulo 13. Using the extended Euclidean algorithm or by checking: 7⋅2=14≡1(mod13)7 \cdot 2 = 14 \equiv 1 \pmod{13}. So 7−1≡2(mod13)7^{-1} \equiv 2 \pmod{13}. Therefore, x≡2⋅11≡22≡9(mod13)x \equiv 2 \cdot 11 \equiv 22 \equiv 9 \pmod{13}. Choice A (6) comes from incorrectly computing 11−7+211 - 7 + 2. Choice C (11) assumes x≡bx \equiv b. Choice D (12) results from computing 13−113 - 1 incorrectly.

Question 10

If x2≡1(mod8)x^2 \equiv 1 \pmod{8}, how many solutions for xx exist in the range 0≤x<80 \leq x < 8?

  1. 1
  2. 2
  3. 3
  4. 4 (correct answer)
Explanation: We need to find all xx in {0,1,2,3,4,5,6,7}\{0,1,2,3,4,5,6,7\} such that x2≡1(mod8)x^2 \equiv 1 \pmod{8}. Testing each value: 02=0≢10^2 = 0 \not\equiv 1, 12=1≡11^2 = 1 \equiv 1 ✓, 22=4≢12^2 = 4 \not\equiv 1, 32=9≡13^2 = 9 \equiv 1 ✓ (since 9=8+19 = 8 + 1), 42=16≡0≢14^2 = 16 \equiv 0 \not\equiv 1 (since 16=2⋅816 = 2 \cdot 8), 52=25≡15^2 = 25 \equiv 1 ✓ (since 25=3⋅8+125 = 3 \cdot 8 + 1), 62=36≡4≢16^2 = 36 \equiv 4 \not\equiv 1 (since 36=4⋅8+436 = 4 \cdot 8 + 4), 72=49≡17^2 = 49 \equiv 1 ✓ (since 49=6⋅8+149 = 6 \cdot 8 + 1). So the solutions are x∈{1,3,5,7}x \in \{1,3,5,7\}, giving 4 solutions. Choice A (1) would result from only finding x=1x = 1. Choice B (2) might come from only finding x∈{1,7}x \in \{1,7\} by thinking x≡±1(mod8)x \equiv \pm 1 \pmod{8}. Choice C (3) could result from missing one solution due to computational error.

Question 11

What is the multiplicative order of 5 modulo 13?

  1. 4 (correct answer)
  2. 6
  3. 12
  4. 13
Explanation: The multiplicative order of 5 modulo 13 is the smallest positive integer kk such that 5k≡1(mod13)5^k \equiv 1 \pmod{13}. We compute powers of 5: 51≡5(mod13)5^1 \equiv 5 \pmod{13}, 52=25≡12(mod13)5^2 = 25 \equiv 12 \pmod{13} (since 25=13+1225 = 13 + 12), 53=5⋅12=60≡8(mod13)5^3 = 5 \cdot 12 = 60 \equiv 8 \pmod{13} (since 60=4⋅13+860 = 4 \cdot 13 + 8), 54=5⋅8=40≡1(mod13)5^4 = 5 \cdot 8 = 40 \equiv 1 \pmod{13} (since 40=3⋅13+140 = 3 \cdot 13 + 1). Therefore, the order is 4. Choice B (6) might come from confusing this with ϕ(13)/2=6\phi(13)/2 = 6. Choice C (12) would be the result if 5 were a primitive root (which it's not since ϕ(13)=12\phi(13) = 12 and 54≡15^4 \equiv 1). Choice D (13) is impossible since the order must divide ϕ(13)=12\phi(13) = 12.

Question 12

How many solutions does the congruence 6x≡9(mod15)6x \equiv 9 \pmod{15} have?

  1. 0
  2. 1
  3. 3 (correct answer)
  4. 5
Explanation: For the linear congruence ax≡b(modn)ax \equiv b \pmod{n}, the number of solutions is gcd⁡(a,n)\gcd(a,n) if gcd⁡(a,n)\gcd(a,n) divides bb, and 0 otherwise. Here, gcd⁡(6,15)=3\gcd(6,15) = 3. Since 33 divides 99, there are exactly 33 solutions modulo 1515. To find them, we first divide the entire congruence by 33: 2x≡3(mod5)2x \equiv 3 \pmod{5}. Since gcd⁡(2,5)=1\gcd(2,5) = 1, this has a unique solution modulo 55. We need 2−1(mod5)2^{-1} \pmod{5}. Since 2⋅3=6≡1(mod5)2 \cdot 3 = 6 \equiv 1 \pmod{5}, we have 2−1≡3(mod5)2^{-1} \equiv 3 \pmod{5}. Thus x≡3⋅3=9≡4(mod5)x \equiv 3 \cdot 3 = 9 \equiv 4 \pmod{5}. The solutions modulo 1515 are x≡4,4+5,4+10≡4,9,14(mod15)x \equiv 4, 4+5, 4+10 \equiv 4, 9, 14 \pmod{15}. Choice A (0) would result from incorrectly thinking gcd⁡(6,15)=3\gcd(6,15) = 3 doesn't divide 99. Choice B (1) ignores the multiplicity. Choice D (5) might come from thinking the number of solutions is 15/gcd⁡(6,15)=515/\gcd(6,15) = 5.