アルゴリズム論特論(塩田)第5回 (3) 九去法
九去法
$\bmod 9$ の法演算を応用した検算法を紹介しましょう。 原理 $\bmod 9$ では $\textcolor{blue}{10 \equiv 1}$, $\textcolor{red}{9 \equiv 0}$ なので、 \begin{eqnarray*} 367 &=& 3 \times \textcolor{blue}{10}^2 + 6 \times \textcolor{blue}{10} + 7 \\ &\equiv& 3 \times \textcolor{blue}{1}^2 + 6 \times \textcolor{blue}{1} + 7 \\ &\equiv& 3+6+7 = (\textcolor{red}{3+6})+7 \equiv 7 \pmod{9},\\ 52 &=& 5 \times \textcolor{blue}{10} + 2 \\ &\equiv& 5 \times \textcolor{blue}{1} + 2 \equiv 7 \pmod{9},\\ 19084 &=& 1 \times \textcolor{blue}{10}^4 + 9 \times \textcolor{blue}{10}^3 + 8 \times \textcolor{blue}{10} + 4 \\ &\equiv& 3 \times \textcolor{blue}{1}^4 + 9 \times \textcolor{blue}{1}^3 + 8 \times \textcolor{blue}{1} + 4 \\ &\equiv& 1 + 9 + 8 + 4 = (\textcolor{red}{1+8}) + \textcolor{red}{9} + 4 \equiv 4 \pmod{9}\\ \end{eqnarray*} という計算ができ、