Find the remainder in the division of $3^{385}$ by $400$. Find the remainder in the division of $3^{385}$ by $400$.
What I thought:
I'm looking for the smallest $r$ such that $3^{385} \equiv r \pmod {400}$. Which is equivalent to the system $\begin{cases} 3^{385} \equiv r \pmod {2^4} \\ 3^{385} \equiv r \pmod {5^2}\end{cases}$. Obviously, $3^{385} \equiv 1 \pmod {2}$. Using Fermat's Little Theorem,  $3^{385} \equiv 3^1 \pmod {5}$ since $385 \equiv 1 \pmod 4$. However, I'm not sure how to extend this to the original system. I've figured that $r \mod 2^4 \in \{1,3,5,7,9,11,13,15\}$ and $r \mod 5^2\in \{3,8,13,18,23\}$. But how do I know which?
Thanks for the help!!
Edit: Look, I should have clarified this earlier: there are too many ways to solve this, and I in fact know many of them. What I need is a follow up on what I have done. How do I solve the system of congruences when the factors of the original modulus are powers?
 A: $$3^{385} = 243^{77}$$
$$\text{We must compute} \; 243^{76}\cdot 243 \; \text{mod}\,(400)$$
$$\Rightarrow 243^{(4\cdot19)} \cdot 243 \; \text{mod}\,(400)$$
$$= (243^4)^{19}\; \text{mod}\,(400) \cdot 243 \; \text{mod}\,(400)$$
$$= (1)^{19} \; \text{mod}\,(400) \cdot 243 \; \text{mod}\,(400)$$
$$= 243 \; \text{mod}\,(400)$$
$$\boxed{\therefore 3^{385} \equiv 243 \; \text{mod}\,(400)}$$
A: Reduced totient for 400 is 20.
So $3^{20} \equiv 1\mod400$ per Carmichael's Theorem.
Hence $3^{380} \equiv 1\mod400$, which implies $3^{385} \equiv 3^5 = 243\mod400$.
A: Hint:
$$3^{385}\equiv 3^{385\bmod\operatorname{order}(3\bmod 400)}\mod 400.$$
Further,  the order of $3$ modulo $400$ is the l.c.m.  of its orders $\bmod 25$ and $\bmod 16$.
A: You are on the right track. But when a prime power ($2^4$ or $5^2$ in this instance) divides the modulus, you have to compute the answer modulo each prime power.
So you have to compute $3^{385} \bmod 16$ and $3^{385}\bmod 25$. We have $\varphi(16)=8$ and $\varphi(25)=20$; can you take it from there?
