# 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 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?

• $10^{400}=1000^{133}\times10$, not $1000^{333}\times10$. Commented Oct 9, 2012 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}$. Commented Oct 9, 2012 at 5:24
• Commented Jun 17, 2016 at 8:22

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

Since $$199$$ is prime and $$\gcd(10,199) = 1$$

So, $$10^{198} \equiv 1 \pmod{199}$$

Squaring the both side: $$10^{396} \equiv 1 \pmod{199}$$

Now: $$10^3 \equiv 5\pmod{199}$$

$$10^{4} \equiv 50 \pmod{199}$$

$$10^{400} \equiv 50 \pmod{199}$$

So, the remainder is $$50$$. This method is known as Euler's Totient

• 1. There is totally redundant to mention $gcd(10,199)=1$. 2. I found in this question that presumably the reason why you posted this answer is just because you want to get started at this site. However, posting an answer to a question that had had an accepted answer 5 years ago helps neither the OP nor yourself. Try to answer some questions that not yet have an accepted answer yet.
– BAI
Commented Oct 19, 2017 at 11:25
• Sorry new to the site as you have mentioned too, I forgot to check the date of the question. Thank you for your guidance. Commented Oct 19, 2017 at 11:27
• The date is not really the point. Surely, if you find an appropriate question which still have no answer, you are very welcome to share your delightful idea, if any. The point is that it is worthless to post an answer under an old question that already had an identical accepted answer.
– BAI
Commented Oct 19, 2017 at 11:44