+0

# Number Theory

0
95
2

What is the remainder when 333^{333} is divided by 13?

Apr 19, 2022

#1
+115
-3

I believe that your answer would be 25 and a remainder of 8

sincerely ▄︻デ✞☬🇮‌🇫‌1️⃣🇳‌1️⃣🇹‌¥☬✞══━一

Apr 19, 2022
#2
+9459
+1

Note that $$\varphi(13) = 13 - 1 = 12$$, where $$\varphi$$ denotes the Euler totient function.

Now, for these type of problems, you can take mod 13 of the base and mod $$\varphi(13)$$ of the power.

$$\begin{array}{rcl} 333^{333} &\equiv& 8^9 \pmod{13}\\ &=& 2^{27} \pmod{13}\\ &=& 2^3 \pmod{13} \end{array}$$

Note that I used $$8^9 = (2^3)^9 = 2^{27}$$ and then took mod $$\varphi(13)$$ of the power again.

Now the size of the problem becomes manageable, because you can calculate 2^3, and that's the answer.

Apr 19, 2022