Question

Use Fermat’s little theorem to evaluate${\mathbf{9}}^{\mathbf{200}}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{19}$

Short answer

$9^{200}mod19=5$

Step-by-step solution

Fermat’s little Theorem

Which says that,Ifpis a prime,m is any integer and$\mathit{p}\boxed{\mathbf{/}}\mathbf{}\mathit{m}$ then${\mathbf{m}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{p}\mathbf{)}$.

Evaluating 9200 mod 19

Here we have $m=9$, and$p=19$

Now, by Fermat’s little theorem we have,

$9^{18}\equiv 1(mod19)$

Now,

$$\begin{gathered} 9^{200}=9^{(18\cdot 11)+2} \\ =9^{(18\cdot 11)}\cdot 9^2 \\ \equiv 1\cdot 9^2(mod19) \\ \equiv 81(mod19) \\ \equiv 5(mod19) \end{gathered}$$

Hence, $9^{200}mod19=5$.