Calculate $121^{199} \mod 300$ Using Fermat's little theorem I proved that

$$121^{199} = 121^{39} \mod 300$$

(as $\phi(300)$ is $80$) but I don't think I can leave it like this. 
My question being how can I solve $121^{39}\hspace{-3mm}\mod 300$. Any ideas, suggestions?
 A: Probably not better than Jyrki's method, but I'm stating it anyway.  First of all, you've overlooked that you're dealing with a square number.  So
$$121^{39}\equiv11^{78}\equiv11^{-2}\pmod{300}$$
$11$ has a rather easy divisibility test, so it's not that hard to find a multiple of $11\equiv1\pmod{300}$.  A $3$-digit number won't work as the sum of the first digit and $1$ cannot possibly be a multiple of $11$.  Among $4$-digit numbers starting with $1$, the only multiple of $11$ is $1001$ which doesn't work.  For a first digit of $2$, on the other hand, we have $2101$ ($2-1+0-1=0$).
$$\frac{2101}{11}=191\equiv-109\pmod{300}$$
Now that we have the inverse of $11$, we just have to square it.
$$(-109)^2=10000+1800+81=11881=11700+181$$
A: The Chinese Remainder Theorem is your friend:


*

*Calculate the result modulo $100$ (the order of $121$ modulo $100$ is a single-digit integer)

*Calculate the result modulo $3$.

*This is enough to know the answer modulo $3\cdot100$ as $\gcd(3,100)=1.$



[Edit 2702]
Others have given solutions based on Euler's totient function. While that is often an indispensable tool in attacking problems like this, I believe in stretching the limitations of elementary tools. In spite of such solutions being a bit ad hoc. 
Concepts originating from elementary group theory are very useful to have, and form a way of distilling what we have learned over the centuries. But for the developing mathematical mind an adventure in experimenting has its merits. I recall having worked out remainders like this in school without any deeper concepts - some of those one only learns to appreciate later. What follows is a result of such experimentation. Of course, mixed with the hindsight of having learned about CRT and such.
Modulo $100$ we have $121\equiv21$. The key shortcut here comes from the trivial observation that $10^2=100\equiv0$. Therefore all but the constant and the linear terms vanish modulo $100$ whenwe apply the binomial theorem
$$
\begin{aligned}
21^n&=(1+20)^n=1+\binom{n}1 20+\binom{n}2 20^2+\cdots\\
&\equiv 1+20\cdot n\pmod{100}.
\end{aligned}
$$
Therefore
$$21^{199}\equiv1+199\cdot20\equiv81\pmod {100}.$$
Modulo $3$ things are trivial. $121\equiv1\pmod3$, so $121^{199}\equiv1\pmod3$ also.
The above modulo $100$ calculation tells us that the remainder modulo $300$ is either $81$, $181$ or $281$. Of these only $181$ is congruent to $1$ modulo $3$, so that is the answer.

Polonius: "Though this be madness, there's method in't."

A: On second thought, maybe a combination of the 2 previous methods is best.  Again
$$121^{39}\equiv11^{78}\equiv11^{-2}\equiv121^{-1}\pmod{300}$$
And now use the Chinese remainder theorem to find the inverse of $121$.  We have
$$121\equiv-4\pmod{25}\text{ and }121\equiv1\pmod{12}$$
So our inverse is equivalent to $6\pmod{25}$ and $1\pmod{12}$.
A: ${\rm mod}\ 25\!:\ \overbrace{11^{20}\equiv 1}^{\large\rm Euler\ \varphi}\,\Rightarrow\, x = 11^{398}\equiv \dfrac{1}{11^2}\equiv \dfrac{-24}{-4}\equiv \color{}6\iff x = \color{#0a0}{6\!+\!25n}$ 
${\rm mod}\ 12\!:\ 11^{398}\equiv (-1)^{398}\equiv \underbrace{1\equiv \color{#0a0}{6\!+\!25n}\equiv 6\!+\!n}_{\Large n\ \equiv\ -5\ \equiv\ \color{#c00}7}\ \Rightarrow\ x = 6\!+\!25(\underbrace{\color{#c00}7\!+\!12k}_{\Large n}) = 181+300k$
