# Find the remainder when $10^{400}$ is divided by 199?

I am trying to solve a problem

Find the remainder when the $10^{400}$ is divided by 199?

I tried it by breaking $10^{400}$ to $1000^{133}*10$ .

And when 1000 is divided by 199 remainder is 5.

So finally we have to find a remainder of :

$5^{133}*10$

But from here i could not find anthing so that it can be reduced to smaller numbers.

How i can achieve this?

Is there is any special defined way to solve this type of problem where denominator is a big prime number?

$10^{400}=1000^{133}\times10$, not $1000^{333}\times10$. – Gerry Myerson Oct 9 '12 at 4:53
A standard beginning (for prime moduli) is to use the fact that if $p$ does not divide $a$, then $a^{p-1}\equiv 1\pmod{p}$. Thus $10^{198}\equiv 1\pmod{199}$. It follows that $10^{396}\equiv 1\pmod{199}$ and therefore $10^{400}\equiv 10^4\pmod{199}$. Now we have to calculate. In this case, there is a further shortcut, since $1000=(5)(199)+5\equiv 5\pmod{199}$. – André Nicolas Oct 9 '12 at 5:24
You can use Fermat's little theorem. It states that if $n$ is prime then $a^n$ has the same remainder as $a$ when divided by $n$.
So, $10^{400} = 10^2 (10^{199})^2$. Since $10^{199}$ has remainder $10$ when divided by $199$, the remainder is therefore the same as the remainder of $10^4$ when divided by $199$. $10^4 = 10000 = 50*199 + 50$, so the remainder is $50$.