[Math] Find the remainder when $10^{400}$ is divided by 199

elementary-number-theorymodular arithmetic

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 anything so that it can be reduced to smaller numbers.

How can I achieve this?

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

Thanks in advance.

Best Answer

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$.

Related Question