# Elementary Number Theory Problems 4.3 Solution (David M. Burton's 7th Edition) - Q1

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

## Background

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

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{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$$$$

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{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$$$$

Therefore,

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

## The rest is for Premium Members only

Subscribe

Already have an account? Log in