Use the binary exponentiation algorithm to compute 19^{53} mod 503

Background

All theorems, corollaries, and definitions listed in the book's order:

Theorems and Corollaries in Elementary Number Theory

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 4)

RanblogRan

I will only use theorems or facts that are proved before this question. So, you will not see that I quote theorems or facts from the later chapters.

Question

Use the binary exponentiation algorithm to compute both $19^{53} \pmod {503}$ and $141^{47} \pmod {1537}$.

Solution

For $19^{53} \pmod {503}$:

$$ \begin{equation} \begin{split} 19^{53} & = 19^{(110101)_{2}} \\ & = 19^{32 + 16 + 4 + 1} \\ & = 19^{32} \cdot 19^{16} \cdot 19^{4} \cdot 19 \pmod {503} \\ \end{split} \nonumber \end{equation} $$

Thus, we obtain the power $19^{2^{j}} \pmod {503}$ for $0 \leq j \leq 5$ by repeatedly squaring while at each stage reducing each result modulo $503$:

$$ \begin{equation} \begin{split} 19^{2} & \equiv 361 \pmod {503} \\ 19^{4} & \equiv (19^{2})^2 \equiv 361^{2} \equiv 130321 \equiv 44 \pmod {503} \\ 19^{8} & \equiv (19^{4})^{2} \equiv 44^{2} \equiv 1936 \equiv 427 \pmod {503} \\ 19^{16} & \equiv (19^{8})^{2} \equiv 427^{2} \equiv 182329 \equiv 243 \pmod {503} \\ 19^{32} & \equiv (19^{16})^{2} \equiv 243^{2} \equiv 59049 \equiv 198 \pmod {503} \\ \end{split} \nonumber \end{equation} $$

Therefore,

$$ \begin{equation} \begin{split} 19^{53} & = 19^{32} \cdot 19^{16} \cdot 19^{4} \cdot 19 \\ & \equiv 198 \cdot 243 \cdot 44 \cdot 19 \\ & \equiv 406 \pmod {503} \end{split} \nonumber \end{equation} $$