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:
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)
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} $$The rest is for Premium Members only
SubscribeAlready have an account? Log in
%20-%20Q1){kind=link}