Hey guys, if i had a question of say:
QUESTION: find the remainders when the following numbers are divided by 89.
i) $\displaystyle 809$
ii) $\displaystyle 800^8$
is there an easy was to work this out?
thanks!
First note that $\displaystyle -a\equiv b-a\pmod{b}$.
It is easy to see that 10 * 89 = 809 + 81. Move 81 to the left side and consider both sides modulo 89.
If you represent 800 as $\displaystyle a * 89 + b$, then $\displaystyle 800^8=(a * 89 + b)^8$. By the Binomial theorem (or just by expanding) one sees that all terms have the factor 89 except for the last one, namely, $\displaystyle b^8$.