Question on modular arithmetic How does one calculate $3^{(29^{10001})} \mod 35$? I'm just not seeing how to start on it, unless someone could give me a hint? Thanks!
 A: Hint: To use Euler's theorem, you need to compute $29^{10001} \bmod \phi(35)$, noting that $\phi(35)=24$.
A: Use first the Chinese remainder theorem and compute first $3^{29^{10001}}$ mod. $5$ and mod.$7$.
 Note that, by lil' Fermat 
$$3^{29^{\scriptstyle 10001}}\equiv3^{29^{\scriptstyle10001} \bmod4}\pmod5,\qquad3^{29^{\scriptstyle 10001}}\equiv3^{29^{\scriptstyle10001} \bmod6}\pmod7. $$ 
Now $29\equiv 1\pmod4$, so $3^{29^{\scriptstyle10001} \bmod4}\equiv 3^1=3\pmod5$.
Similarly, $29\equiv -1\pmod6$, so  $3^{29^{\scriptstyle10001} \bmod4}\equiv 3^{-1}\equiv 5\pmod7$.
Finally everything comes down to solving the system of congruences \begin{cases}
x\equiv3\pmod5,\\x\equiv 5\pmod 7.\end{cases}
As a Bézout's relation between $7$ and $5$ is $\;3\cdot5-2\cdot7=1$, t-he solution is
$$x\equiv 5(3\cdot5)-3(2\cdot 7)=33\pmod{35}. $$
A: Using Carmichael Function,
$$3^{29^{2n+1}}\equiv3^{29^{2n+1}\pmod{\lambda(35)}}\pmod{35}$$
Now as $\lambda(35)=12$ and $29\equiv5\pmod{12},29^{2n+1}\equiv5^{2n+1}$
as $\lambda(12)=2,2n+1\equiv1\pmod2\implies5^{2n+1}\equiv5^1\pmod{12}$
$$\implies3^{29^{2n+1}}\equiv3^5\pmod{35}\equiv?$$
