Having trouble trying to understand how to tackle this question. $19^{16} \mod{20413}$. When approaching this question I understand the steps involved such as $19^{16} / 20413 = 1.413028039\cdot10^{16}$. However not sure what to subtract this answer to achieve a $0$ before the decimal point in order to multiply by $20413$ to get the answer. From the answer sheet the intended answer is $11546$.
Appreciate the help.
On
From a simple minded standpoint, what they’re asking you to do is calculate $19^{16}$, which is equal to $288441413567621167681$, divide by $20413$, and give the remainder as your answer. Needless to say, you can’t do this on a calculator. By hand, if you’ve remembered how to do long division, you’ll get $11546$.
But since $20413$ is not prime, but rather equal to $137\cdot149$, this can also be done by making use of the Chinese Remainder Theorem. All in all, I think the most efficient way is just what @JWTanner has given you.
$$19^2=361$$ $$19^4=361^2=130321\equiv 7843 \pmod {20413}$$ $$19^8\equiv 7843^2 \equiv 8280 \pmod {20413}$$ $$19^{16}\equiv 8280^2\equiv 11546 \pmod {20413}$$