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

2 Answers 2

Reset to default
8
$\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$
0
-3
$\begingroup$

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

$\endgroup$
3
  • 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
    Commented Oct 19, 2017 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
    Commented Oct 19, 2017 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
    Commented Oct 19, 2017 at 11:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .