whats is the remainder when $38^{33^{41}}$ is divided by $11$?

Question

What kind approach is to solve this kind of questions? I have already tried break down and squaring. But still stuck.

Answer 1

$38 \equiv 5 \mod 11$. Its multiplicative order mod $11$ is $5$, i.e. $5^5 \equiv 1 \mod 11$. So next you want to compute $33^{41} \mod 5$.

Answer 2

$38\equiv5\pmod{11}$ so we need to calculate $5^{33^{41}}\pmod{11}$ For the exponent we need to know the smallest positive integer $n$ such that $5^n\equiv1\pmod{11}$ By Fermat's little theorem, $5^{10}\equiv1\pmod{11}$ and the smallest $n$ must be a divisor of $10,$ so $n$ is one of $2,5,10.$ We have $$\begin{align}5^2&=25\equiv3\pmod{11}\\5^4&\equiv9\implies5^5\equiv45\equiv1\pmod{11}\end{align},$$ so that $n=5$.

Now we need to know the congruence class of $33^{41}\pmod{5}$ Use the same method as above.

Answer 3

By lil' Fermat, $$38^{33^{41}}\equiv38^{33^{41}\bmod 10}\equiv 5^{33^{41}\bmod 10}\equiv 5^{3^{41}\bmod 10}\mod11.$$ To end the computation, we need to know the order of $3\mod 40$. As $\varphi(10)=\varphi(2)\varphi(5)=4$, we know it's a divisor of $4$, so $\;3^{41}\equiv 3\mod 10$. Ultimately, it comes down to computing $5^3\bmod 11$, which shouldn't be too long.