3
$\begingroup$

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.

  • 0
    See also: [How do I compute $a^b\,\bmod c$ by hand?](http://math.stackexchange.com/questions/81228/how-do-i-compute-ab-bmod-c-by-hand)2016-06-17

2 Answers 2

7

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

-1

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

So, $10^{198} \equiv 1 (mod 199)$

Squaring the both side: $10^{396} \equiv 1 (mod 199)$

Now: $10^3 \equiv 5(mod199)$

$10^{4} \equiv 50 (mod 199)$

$10^{400} \equiv 50 (mod 199)$

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

  • 0
    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.2017-10-19