Now Playing
Ambient Radio

Keep Learning?

Sign in to continue practicing.

Remainders
Find the remainder when $17^{17^{17}}$ is divided by 13.\n\nA) 4\nB) 7\nC) 10\nD) 12
Correct Option: C\n\nTo find the remainder when $17^{17^{17}}$ is divided by 13, we need to evaluate $17^{17^{17}} \\pmod{13}$.\n\nStep 1: Simplify the base modulo 13.\nFirst, we observe that $17 \\equiv 4 \\pmod{13}$.\nSo, the expression can be rewritten as $4^{17^{17}} \\pmod{13}$.\n\nStep 2: Apply Euler's Totient Theorem or Fermat's Little Theorem.\nSince 13 is a prime number, we can use Fermat's Little Theorem, which states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have $a^{p-1} \\equiv 1 \\pmod{p}$.\nHere, $p=13$, so $a^{12} \\equiv 1 \\pmod{13}$ for any $a$ not divisible by 13. This implies that we need to evaluate the exponent modulo $\phi(13)$, where $\phi(13) = 13-1 = 12$.\nTherefore, we need to find the remainder of the exponent $17^{17}$ when divided by 12.\n\nStep 3: Calculate the exponent $17^{17} \\pmod{12}$.\nFirst, simplify the base of this inner exponent: $17 \\equiv 5 \\pmod{12}$.\nSo, we need to compute $5^{17} \\pmod{12}$.\nLet's determine the cyclicity of powers of 5 modulo 12:\n$5^1 \\equiv 5 \\pmod{12}$\n$5^2 = 25 \\equiv 1 \\pmod{12}$\nThe cycle length for powers of 5 modulo 12 is 2. This means that $5^k \\pmod{12}$ depends on $k \\pmod{2}$.\n\nNow, we find the remainder of the exponent 17 when divided by the cycle length 2:\n$17 \\equiv 1 \\pmod{2}$.\n\nTherefore, $5^{17} \\equiv 5^1 \\equiv 5 \\pmod{12}$.\nThis implies that $17^{17} \\equiv 5 \\pmod{12}$.\n\nStep 4: Substitute the simplified exponent back into the main expression.\nWe established that $17^{17^{17}} \\pmod{13} \\equiv 4^{17^{17}} \\pmod{13}$.\nSince $17^{17} \\equiv 5 \\pmod{12}$, we can replace the exponent $17^{17}$ with 5 (as per Euler's Totient Theorem).\nSo, we need to calculate $4^5 \\pmod{13}$.\n\nStep 5: Calculate $4^5 \\pmod{13}$.\n$4^1 \\equiv 4 \\pmod{13}$\n$4^2 = 16 \\equiv 3 \\pmod{13}$\n$4^3 = 4^2 \\times 4 \\equiv 3 \\times 4 = 12 \\equiv -1 \\pmod{13}$\n$4^4 = (4^2)^2 \\equiv 3^2 = 9 \\pmod{13}$ (Alternatively, $4^4 = 4^3 \\times 4 \\equiv -1 \\times 4 = -4 \\equiv 9 \\pmod{13}$)\n$4^5 = 4^4 \\times 4 \\equiv 9 \\times 4 = 36 \\pmod{13}$\nTo find the remainder of 36 divided by 13: $36 = 2 \\times 13 + 10$.\nSo, $36 \\equiv 10 \\pmod{13}$.\n\nThus, the remainder when $17^{17^{17}}$ is divided by 13 is 10.\n\nThe final answer is 10.
100%