Question

a) Use Fermat’s little theorem to compute ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{7}$and ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{11}\mathbf{\text{and}}{\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{13}$

b) Use your results from part (a) and the Chinese remainder theorem to find ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{1001}$. (Note that$\mathbf{}\mathbf{1001}\mathbf{=}\mathbf{7.11.13}$)

Short answer

$A)\mathbf{}{\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{7}\mathbf{=}\mathbf{3}\mathbf{;}{\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{11}\mathbf{=}\mathbf{4}\mathbf{;}{\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{13}\mathbf{=}\mathbf{8}$

B) ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{1001}\mathbf{=}\mathbf{983}$

Step-by-step solution

 Fermat’s little theorem    

FERMAT’S LITTLE THEOREM tells us that If $\mathit{p}$, is prime and $\mathit{a}$is an integer not divisible by $\mathit{p}$

Then ${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$

To find 52003mod7

By Fermat’s little theorem we know that,

${\mathbf{5}}^{\mathbf{6}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{7}$

So,

${\left(5^6\right)}^k\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{7}$for every positive integer $\mathit{k}$

To take advantage of this last congruence, we divide the exponent $\mathbf{2003}$by $\mathbf{6}$,

finding that

$\mathbf{2003}\mathbf{=}\mathbf{333}\mathbf{\times }\mathbf{6}\mathbf{+}\mathbf{5}$

.

We now see that

$\mathbf{2003}\mathbf{=}\mathbf{333}\mathbf{\times }\mathbf{6}\mathbf{+}\mathbf{5}$

$$\begin{gathered} \mathbf{=}{\left(5^6\right)}^{\mathbf{333}}{\mathbf{5}}^{\mathbf{5}}\mathbf{mod}\mathbf{7} \\ \mathbf{=}\mathbf{(}\mathbf{1}{\mathbf{)}}^{\mathbf{333}}{\mathbf{5}}^{\mathbf{5}}\mathbf{mod}\mathbf{7}\left(\text{Since}{5}^6\equiv 1\right) \\ \mathbf{=}{\mathbf{5}}^{\mathbf{5}}\mathbf{mod}\mathbf{7} \\ \mathbf{=}\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{)} \end{gathered}$$

Therefore, ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{7}$is $\mathbf{3}$

To find 52003mod11

1. By Fermat’s little theorem

${\mathbf{5}}^{\mathbf{6}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{7}\mathbf{}$

So,

${\mathbf{\left(}{\mathbf{5}}^{\mathbf{10}}\mathbf{\right)}}^{\mathbf{k}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{11}$

We divide the exponent $\mathbf{2003}$by $\mathbf{10}$,

$\mathbf{2003}\mathbf{=}\mathbf{40}\mathbf{\times }\mathbf{10}\mathbf{+}\mathbf{3}\mathbf{\text{.}}$

.

We now see that

$$\begin{gathered} {\mathbf{5}}^{\mathbf{2003}}\mathbf{=}{\mathbf{5}}^{\mathbf{40}\mathbf{\times }\mathbf{10}\mathbf{+}\mathbf{3}}\mathbf{mod}\mathbf{11} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}{\left(5^{10}\right)}^{\mathbf{40}}{\mathbf{5}}^{\mathbf{3}}\mathbf{mod}\mathbf{11} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}\mathbf{(}\mathbf{1}{\mathbf{)}}^{\mathbf{40}}{\mathbf{5}}^{\mathbf{3}}\mathbf{mod}\mathbf{11}\left(\text{Since}{5}^{10}\equiv 1\right) \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}{\mathbf{5}}^{\mathbf{3}}\mathbf{mod}\mathbf{11} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}\mathbf{4}\mathbf{(}\mathbf{mod}\mathbf{11}\mathbf{)} \end{gathered}$$

Therefore, ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{11}$is $\mathbf{4}$

To find 52003mod13

By Fermat’s little theorem

${\mathbf{5}}^{\mathbf{12}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{13}$

So,

${\left(5^{12}\right)}^{\mathbf{k}}\mathbf{\equiv }\mathbf{1}\mathbf{mod}\mathbf{13}$

We divide the exponent $\mathbf{2003}$by $\mathbf{12}$,

$\mathbf{}\mathbf{2003}\mathbf{=}\mathbf{166}\mathbf{\times }\mathbf{12}\mathbf{+}\mathbf{3}$

We now see that

$$\begin{gathered} {\mathbf{5}}^{\mathbf{2003}}\mathbf{=}{\mathbf{5}}^{\mathbf{16}\mathbf{(}\mathbf{x}\mathbf{+}\mathbf{12}\mathbf{+}\mathbf{11}}\mathbf{mod}\mathbf{13} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}{\left(5^{12}\right)}^{\mathbf{166}}{\mathbf{5}}^{\mathbf{11}}\mathbf{mod}\mathbf{13}\mathbf{} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{=}\mathbf{(}\mathbf{1}{\mathbf{)}}^{\mathbf{166}}{\mathbf{5}}^{\mathbf{11}}\mathbf{mod}\mathbf{13}\left(\text{Since}{5}^{12}\equiv 1\right) \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\begin{array}{r}\mathbf{=}{\mathbf{5}}^{\mathbf{1}}\mathbf{mod}\mathbf{13}\mathbf{}\\ \mathbf{}\mathbf{=}\mathbf{8}\mathbf{(}\mathbf{mod}\mathbf{13}\mathbf{)}\end{array} \end{gathered}$$

Therefore, ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{13}$is 8

To find 

We know that$\mathbf{1001}\mathbf{=}\mathbf{7}\mathbf{.11.13}$

We need to solve the three congruence’s from part (a)

$\begin{array}{r}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{mod}\mathbf{7}\mathbf{}\mathbf{}\\ \mathbf{x}\mathbf{\equiv }\mathbf{4}\mathbf{mod}\mathbf{11}\\ \mathbf{x}\mathbf{\equiv }\mathbf{8}\mathbf{mod}\mathbf{13}\end{array}$

The first two congruence can be expressed as,

$\begin{array}{r}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{-}\mathbf{7}\mathbf{\times }\mathbf{3}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{x}\mathbf{\equiv }\mathbf{-}\mathbf{18}\mathbf{mod}\mathbf{7}\end{array}$ $\begin{array}{r}\mathbf{x}\mathbf{\equiv }\mathbf{4}\mathbf{-}\mathbf{11}\mathbf{\times }\mathbf{2}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{x}\mathbf{\equiv }\mathbf{-}\mathbf{18}\mathbf{mod}\mathbf{11}\end{array}$

and

Now,

localid="1668663388622" $\begin{array}{r}\mathbf{x}\mathbf{\equiv }\mathbf{-}\mathbf{18}\mathbf{(}\mathbf{mod}\mathbf{7}\mathbf{.11}\mathbf{)}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{x}\mathbf{\equiv }\mathbf{-}\mathbf{18}\mathbf{(}\mathbf{mod}\mathbf{77}\mathbf{)}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\end{array}$

This congruence can be expressed as,

$$\begin{gathered} \mathit{x}\mathbf{\equiv }\mathbf{18}\mathbf{-}\mathbf{77}\mathbf{\times }\mathbf{26} \\ \mathit{x}\mathbf{\equiv }\mathbf{-}\mathbf{2020}\mathbf{mod}\mathbf{77} \end{gathered}$$

The third congruence,

$$\begin{gathered} \mathit{x}\mathbf{\equiv }\mathbf{8}\mathbf{-}\mathbf{13}\mathbf{\times }\mathbf{156} \\ \mathit{x}\mathbf{\equiv }\mathbf{-}\mathbf{2020}\mathbf{mod}\mathbf{13} \end{gathered}$$

Now,

$$\begin{gathered} \mathit{x}\mathbf{\equiv }\mathbf{-}\mathbf{2020}\mathbf{(}\mathbf{mod}\mathbf{77}\mathbf{.13}\mathbf{)} \\ \mathit{x}\mathbf{\equiv }\mathbf{-}\mathbf{2020}\mathbf{(}\mathbf{mod}\mathbf{1001}\mathbf{)} \\ \mathit{x}\mathbf{=}\mathbf{983} \end{gathered}$$

Therefore, ${\mathbf{5}}^{\mathbf{2003}}\mathbf{mod}\mathbf{1001}$is $\mathbf{983}$