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$ 32 Answers
$\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 $\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
