Modular arithmetic operations and congruences - Discrete Math

1. Let $p$ be a prime number greater than 3. If $p^2 \equiv 1 \pmod{24}$, what is the remainder when $p^3$ is divided by 24?
   Answer: 5 Since $p$ is prime and $p > 3$, we have $\gcd(p, 6) = 1$. Also, $p$ is odd, so $p^2$ is odd. For $p^2 \equiv 1 \pmod{24}$, we need $p^2 \equiv 1 \pmod{8}$ and $p^2 \equiv 1 \pmod{3}$. Since $p$ is odd, $p = 2k+1$ for some $k$, so $p^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1$. Since either $k$ or $k+1$ is even, $k(k+1)$ is even, so $4k(k+1) \equiv 0 \pmod{8}$. Thus $p^2 \equiv 1 \pmod{8}$ for any odd $p$. For $p^2 \equiv 1 \pmod{3}$, we need $p \not\equiv 0 \pmod{3}$. Since $p > 3$ is prime, this is satisfied. By Fermat's Little Theorem, $p^2 \equiv 1 \pmod{3}$ when $p \equiv \pm 1 \pmod{3}$. So the condition $p^2 \equiv 1 \pmod{24}$ is satisfied by primes $p > 3$ with $p \equiv \pm 1 \pmod{3}$, which includes $p \equiv 1, 5 \pmod{6}$ (since $p$ must be coprime to 6). Now, $p^3 = p \cdot p^2 \equiv p \cdot 1 = p \pmod{24}$. Since $p$ is a prime greater than 3, the possible values modulo 24 are those coprime to 24. We have $\gcd(n, 24) = 1$ when $n \equiv 1, 5, 7, 11, 13, 17, 19, 23 \pmod{24}$. Among the primes, we could have $p = 5$, giving $p^3 \equiv 5 \pmod{24}$. Let's verify: $5^2 = 25 \equiv 1 \pmod{24}$ ✓. So $p^3 \equiv 5 \pmod{24}$. Choice A assumes $p^3 \equiv (p^2) \cdot p^{-1} \equiv 1 \pmod{24}$. Choice C might come from $p = 11$, but $11^2 = 121 \not\equiv 1 \pmod{24}$. Choice D might assume $p \equiv -1 \pmod{24}$.
2. If $n \equiv 4 \pmod{9}$ and $n^2 \equiv r \pmod{9}$, what is the value of $r$?
   Answer: 7 Since $n \equiv 4 \pmod{9}$, we have $n^2 \equiv 4^2 \equiv 16 \pmod{9}$. Now $16 = 9 + 7$, so $16 \equiv 7 \pmod{9}$. Therefore $r = 7$. Choice A results from incorrectly computing $4^2 - 15$. Choice B assumes $n^2 \equiv n \pmod{9}$. Choice D comes from computing $16 - 8 = 8$ instead of the proper modular reduction.
3. What is the multiplicative order of 5 modulo 13?
   Answer: 4 The multiplicative order of 5 modulo 13 is the smallest positive integer $k$ such that $5^k \equiv 1 \pmod{13}$. We compute powers of 5: $5^1 \equiv 5 \pmod{13}$, $5^2 = 25 \equiv 12 \pmod{13}$ (since $25 = 13 + 12$), $5^3 = 5 \cdot 12 = 60 \equiv 8 \pmod{13}$ (since $60 = 4 \cdot 13 + 8$), $5^4 = 5 \cdot 8 = 40 \equiv 1 \pmod{13}$ (since $40 = 3 \cdot 13 + 1$). Therefore, the order is 4. Choice B (6) might come from confusing this with $\phi(13)/2 = 6$. Choice C (12) would be the result if 5 were a primitive root (which it's not since $\phi(13) = 12$ and $5^4 \equiv 1$). Choice D (13) is impossible since the order must divide $\phi(13) = 12$.
4. If $x \equiv 4 \pmod{15}$ and $y \equiv 11 \pmod{15}$, what is the smallest positive value of $x^2 + y^2$?
   Answer: 137 We have $x = 15k + 4$ and $y = 15j + 11$ for integers $k, j \geq 0$. Then $x^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(k^2 + j^2) + 120k + 330j$. Since all coefficients are positive and $k, j \geq 0$, the minimum occurs at $k = j = 0$. This gives $x^2 + y^2 = 4^2 + 11^2 = 16 + 121 = 137$. Choice B might result from using $x = 4, y = 11$ but adding an extra term. Choice C could come from $x = 19, y = 11$: $19^2 + 11^2 = 361 + 121 = 482$, which doesn't match. Choice D similarly doesn't align with small values.
5. What is the smallest positive integer $n$ such that $2^n \equiv 1 \pmod{35}$?
   Answer: 12 Since $35 = 5 \cdot 7$ and $\gcd(5,7) = 1$, we use the Chinese Remainder Theorem. We need $2^n \equiv 1 \pmod{5}$ and $2^n \equiv 1 \pmod{7}$ simultaneously. For $\bmod 5$: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 3$, $2^4 \equiv 1 \pmod{5}$. So the order of $2$ modulo $5$ is $4$. For $\bmod 7$: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 1 \pmod{7}$. So the order of $2$ modulo $7$ is $3$. The smallest $n$ such that $2^n \equiv 1$ modulo both $5$ and $7$ is $\text{lcm}(4,3) = 12$. Choice A (6) is $4 + 3 - 1$, a common error when adding orders instead of taking the LCM. Choice C (24) is $4 \times 3 \times 2$, possibly from incorrectly computing $\text{lcm}(4,3) \times 2$. Choice D (30) might come from using $\phi(35) = \phi(5)\phi(7) = 4 \cdot 6 = 24$, then adding 6.
6. How many solutions does the congruence $6x \equiv 9 \pmod{15}$ have?
   Answer: 3 For the linear congruence $ax \equiv b \pmod{n}$, the number of solutions is $\gcd(a,n)$ if $\gcd(a,n)$ divides $b$, and 0 otherwise. Here, $\gcd(6,15) = 3$. Since $3$ divides $9$, there are exactly $3$ solutions modulo $15$. To find them, we first divide the entire congruence by $3$: $2x \equiv 3 \pmod{5}$. Since $\gcd(2,5) = 1$, this has a unique solution modulo $5$. We need $2^{-1} \pmod{5}$. Since $2 \cdot 3 = 6 \equiv 1 \pmod{5}$, we have $2^{-1} \equiv 3 \pmod{5}$. Thus $x \equiv 3 \cdot 3 = 9 \equiv 4 \pmod{5}$. The solutions modulo $15$ are $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$ doesn't divide $9$. Choice B (1) ignores the multiplicity. Choice D (5) might come from thinking the number of solutions is $15/\gcd(6,15) = 5$.
7. If $a \equiv 7 \pmod{13}$ and $b \equiv 11 \pmod{13}$, what is the smallest positive integer $x$ such that $ax \equiv b \pmod{13}$?
   Answer: 9 We need to solve $7x \equiv 11 \pmod{13}$. First, we find the multiplicative inverse of 7 modulo 13. Using the extended Euclidean algorithm or by checking: $7 \cdot 2 = 14 \equiv 1 \pmod{13}$. So $7^{-1} \equiv 2 \pmod{13}$. Therefore, $x \equiv 2 \cdot 11 \equiv 22 \equiv 9 \pmod{13}$. Choice A (6) comes from incorrectly computing $11 - 7 + 2$. Choice C (11) assumes $x \equiv b$. Choice D (12) results from computing $13 - 1$ incorrectly.
8. Find the number of solutions to $6x \equiv 9 \pmod{15}$ where $0 \leq x < 15$.
   Answer: 3 For $ax \equiv b \pmod{m}$ to have solutions, we need $\gcd(a,m) | b$. Here $\gcd(6,15) = 3$ and $3 | 9$, so solutions exist. The number of solutions is $\gcd(6,15) = 3$. To find them, we first solve $\frac{6}{3}x \equiv \frac{9}{3} \pmod{\frac{15}{3}}$, which gives $2x \equiv 3 \pmod{5}$. Since $2 \cdot 3 = 6 \equiv 1 \pmod{5}$, we have $x \equiv 3 \cdot 3 \equiv 4 \pmod{5}$. So $x \in \{4, 9, 14\}$. Choice A assumes no solutions exist. Choice B counts only one fundamental solution. Choice D incorrectly uses $\phi(15) = 8$ somehow.
9. If $a \equiv 13 \pmod{17}$ and $b \equiv 8 \pmod{17}$, what is $(a - 2b)^2 \pmod{17}$?
   Answer: 9 First, compute $a - 2b \equiv 13 - 2(8) \equiv 13 - 16 \equiv -3 \equiv 14 \pmod{17}$. Then $(a - 2b)^2 \equiv 14^2 \equiv 196 \pmod{17}$. Since $196 = 11 \cdot 17 + 9$, we have $196 \equiv 9 \pmod{17}$. Choice A results from computing $(-3)^2 = 9$ but then incorrectly reducing $9 - 5$. Choice C comes from computing $13 - 1 = 12$ incorrectly. Choice D assumes $(14)^2 \equiv (-3)^2 \equiv 16$ by forgetting the modular reduction.
10. What is the last two digits of $3^{100}$?
    Answer: 01 We need $3^{100} \pmod{100}$. Using Euler's theorem, $\phi(100) = \phi(4) \cdot \phi(25) = 2 \cdot 20 = 40$. Since $\gcd(3, 100) = 1$, we have $3^{40} \equiv 1 \pmod{100}$. Therefore $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 $3^{20}$: $3^{10} = 59049 \equiv 49 \pmod{100}$, so $3^{20} \equiv 49^2 = 2401 \equiv 1 \pmod{100}$. Choice B is $3^{10} \pmod{100}$. Choice C results from incorrect exponent arithmetic. Choice D assumes $3^4 = 81$ pattern repeats incorrectly.
11. Find the remainder when $3^{100}$ is divided by 7.
    Answer: 4 We use Fermat's Little Theorem. Since 7 is prime and $\gcd(3,7) = 1$, we have $3^{6} \equiv 1 \pmod{7}$. Now $100 = 6 \cdot 16 + 4$, so $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 $3^4 = 81 = 11 \cdot 7 + 4$, so $3^4 \equiv 4 \pmod{7}$. Choice A (1) would result from incorrectly thinking $3^{100} \equiv 3^{100 \bmod 6} = 3^4 \equiv 1$. Choice B (2) might come from computing $3^2 = 9 \equiv 2 \pmod{7}$ and stopping there. Choice D (6) could result from computing $3^6 \equiv 1$, then incorrectly getting $3^{100} \equiv 3^{100-6} = 3^{94} \equiv 3^1 \cdot 3^{93} \equiv 6$.
12. If $x^2 \equiv 1 \pmod{8}$, how many solutions for $x$ exist in the range $0 \leq x < 8$?
    Answer: 4 We need to find all $x$ in $\{0,1,2,3,4,5,6,7\}$ such that $x^2 \equiv 1 \pmod{8}$. Testing each value: $0^2 = 0 \not\equiv 1$, $1^2 = 1 \equiv 1$ ✓, $2^2 = 4 \not\equiv 1$, $3^2 = 9 \equiv 1$ ✓ (since $9 = 8 + 1$), $4^2 = 16 \equiv 0 \not\equiv 1$ (since $16 = 2 \cdot 8$), $5^2 = 25 \equiv 1$ ✓ (since $25 = 3 \cdot 8 + 1$), $6^2 = 36 \equiv 4 \not\equiv 1$ (since $36 = 4 \cdot 8 + 4$), $7^2 = 49 \equiv 1$ ✓ (since $49 = 6 \cdot 8 + 1$). So the solutions are $x \in \{1,3,5,7\}$, giving 4 solutions. Choice A (1) would result from only finding $x = 1$. Choice B (2) might come from only finding $x \in \{1,7\}$ by thinking $x \equiv \pm 1 \pmod{8}$. Choice C (3) could result from missing one solution due to computational error.

Start this quiz