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.

  • 2
    $10^{400}=1000^{133}\times10$, not $1000^{333}\times10$.2012-10-09
  • 1
    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}$.2012-10-09
  • 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

  • 1
    1. There is totally redundant to mention $gcd(10,199)=1$. 2. I found in [this question](https://math.stackexchange.com/q/2479803/448487) 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.2017-10-19
  • 0
    Sorry new to the site as you have mentioned too, I forgot to check the date of the question. Thank you for your guidance.2017-10-19
  • 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