Now Playing
Ambient Radio

Keep Learning?

Sign in to continue practicing.

Remainders
Find the remainder when $(23)^{101} + (24)^{102} + (25)^{103}$ is divided by $100$. \n\nA. $24$\nB. $23$\nC. $25$\nD. $76$
Correct Answer: A\n\nWe need to find the remainder of $(23)^{101} + (24)^{102} + (25)^{103}$ when divided by $100$.\nLet's evaluate each term individually modulo $100$.\n\n**Term 1: $(23)^{101} \pmod{100}$**\nSince $\gcd(23, 100) = 1$, we can use Euler's Totient Theorem. \nEuler's totient function $\phi(n)$ counts the number of positive integers up to a given integer $n$ that are relatively prime to $n$. \nFor $n=100 = 2^2 \cdot 5^2$, $\phi(100) = \phi(2^2) \cdot \phi(5^2) = (2^2 - 2^1) \cdot (5^2 - 5^1) = (4-2) \cdot (25-5) = 2 \cdot 20 = 40$.\nAccording to Euler's Totient Theorem, if $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod n$.\nSo, $23^{40} \equiv 1 \pmod{100}$.\nWe can write the exponent $101$ as $2 \cdot 40 + 21$. However, finding $23^{21} \pmod{100}$ is still involved. Let's find the order of $23 \pmod{100}$ directly.\n$23^1 \equiv 23 \pmod{100}$\n$23^2 \equiv 529 \equiv 29 \pmod{100}$\n$23^4 \equiv 29^2 \equiv 841 \equiv 41 \pmod{100}$\n$23^5 \equiv 41 \cdot 23 \equiv 943 \equiv 43 \pmod{100}$\n$23^{10} \equiv 43^2 \equiv 1849 \equiv 49 \pmod{100}$\n$23^{20} \equiv 49^2 \equiv 2401 \equiv 1 \pmod{100}$.\nThe order of $23$ modulo $100$ is $20$. Since $101 = 5 \cdot 20 + 1$,\n$23^{101} = (23^{20})^5 \cdot 23^1 \equiv 1^5 \cdot 23 \equiv 23 \pmod{100}$.\n\n**Term 2: $(24)^{102} \pmod{100}$**\nSince $\gcd(24, 100) \neq 1$, Euler's Totient Theorem cannot be directly applied. We use the Chinese Remainder Theorem (CRT) by breaking $100$ into coprime factors, $4$ and $25$.\n\nFirst, modulo $4$:\n$24 \equiv 0 \pmod 4$. So, $24^{102} \equiv 0^{102} \equiv 0 \pmod 4$ (since $102 \ge 1$).\n\nNext, modulo $25$:\n$24 \equiv -1 \pmod{25}$. So, $24^{102} \equiv (-1)^{102} \equiv 1 \pmod{25}$.\n\nNow we need to find a number $X$ such that:\n$X \equiv 0 \pmod 4$\n$X \equiv 1 \pmod{25}$\n\nFrom $X \equiv 1 \pmod{25}$, we can write $X = 25k + 1$ for some integer $k$.\nSubstitute this into the first congruence:\n$25k + 1 \equiv 0 \pmod 4$\nSince $25 \equiv 1 \pmod 4$, this becomes:\n$1k + 1 \equiv 0 \pmod 4$\n$k \equiv -1 \pmod 4$\n$k \equiv 3 \pmod 4$\nSo, $k$ can be written as $4m + 3$ for some integer $m$.\nSubstitute this value of $k$ back into the expression for $X$:\n$X = 25(4m + 3) + 1$\n$X = 100m + 75 + 1$\n$X = 100m + 76$\nTherefore, $X \equiv 76 \pmod{100}$.\nSo, $(24)^{102} \equiv 76 \pmod{100}$.\n\n**Term 3: $(25)^{103} \pmod{100}$**\nThis term also has a base not coprime to $100$. Let's look for a pattern:\n$25^1 = 25 \pmod{100}$\n$25^2 = 625 \equiv 25 \pmod{100}$\n$25^3 \equiv 25 \cdot 25 \equiv 25 \pmod{100}$\nFor any integer exponent $k \ge 1$, $25^k \equiv 25 \pmod{100}$.\nTherefore, $(25)^{103} \equiv 25 \pmod{100}$.\n\n**Combining the remainders:**\nThe remainder of the entire expression is the sum of the individual remainders modulo $100$:\nRemainder $\equiv 23 + 76 + 25 \pmod{100}$\nRemainder $\equiv 99 + 25 \pmod{100}$\nRemainder $\equiv 124 \pmod{100}$\nRemainder $\equiv 24 \pmod{100}$\n\nThe final remainder is $24$.\n\nThe final answer is $\boxed{\text{A}}$
100%