How to find modulo of large numbers like $9801\! \pmod {\!32}$

Question

It is easy to calculate small examples like $26\pmod {5}$ but how do you calculate examples like $9801 \pmod {32}$ without a calculator.

Answer 1

Note $\ {\rm mod}\ 32\!:\,\ \color{#0a0}{100}\equiv\color{#c00}4\ \ \Rightarrow\ \ \begin{align} 9801&\equiv (\color{#0a0}{100}\!-\!2)\cdot \color{#0a0}{100} + 1\\ &\equiv \ \ \ \ (\color{#c00}{4}\!-\!2)\ \cdot\ \color{#c00}4\ +\ 1\\ &\equiv\ \ \ \ 9\end{align}$

If we write an integer in radix $100$ as a polynomial $\ n = P(100) = \sum d_i 100^i $ then

$\qquad {\rm mod}\ 32\!:\,\ \color{#0a0}{100}\equiv\color{#c00}4\,\Rightarrow\, n = P(\color{#0a0}{100})\equiv P(\color{#c00}4)\ $ by the Polynomial Congruence Rule.

In older language this would be called casting-out $32$'s in radix $100$.

For larger numbers it is easier to evaluate $\,P(4)\,$ by the method described here, i.e. continually replace the two most significant radix $100$ digits $\,c,d\,$ by the digit $\, 4c\!+\!d\bmod{32},\,$ so above we replace $\,c,d = 98,01\,$ by $\, 4(98)+01\equiv 4(2)+1\equiv 9\pmod{32}$

Another example $\!\! \underbrace{01,02}_{\large 4(1)+2\,\equiv\,\color{#c00} 6\ \ \ \ \ }\!\!\!\!\!\!\!,10\, \equiv\!\!\!\!\! \underbrace{\color{#c00}6,10}_{\large 4(6)+10\,\equiv\, \color{#0a0}2}\!\!\!\!\!\!\equiv\color{#0a0}2\,\pmod{32} $

Indeed, $ $ dividing: $\ \ 10210\, =\, 319\cdot 32 + \color{#0a0}2$