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.

$\endgroup$
  • 2
    $\begingroup$ $10^{400}=1000^{133}\times10$, not $1000^{333}\times10$. $\endgroup$ – Gerry Myerson Oct 9 '12 at 4:53
  • 1
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Oct 9 '12 at 5:24
  • $\begingroup$ See also: How do I compute $a^b\,\bmod c$ by hand? $\endgroup$ – Martin Sleziak Jun 17 '16 at 8:22
7
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – BAI Oct 19 '17 at 11:25
  • $\begingroup$ Sorry new to the site as you have mentioned too, I forgot to check the date of the question. Thank you for your guidance. $\endgroup$ – Tapan Luthra Oct 19 '17 at 11:27
  • $\begingroup$ 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. $\endgroup$ – BAI Oct 19 '17 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.