倍数の判定方法について考える（前編）〜オイラーの定理で証明する〜

お菓子パーティで個包装のチョコレートを配るときや、友達と外食して割り勘をするときなど、

「数が割り切れるか」

ということを考える場面は少なからずあると思います。

そこで、算数や数学においても重要項目である「倍数の判定方法」について考えたいと思います。

本記事では、教科書や参考書で扱われるような $2,3,4,5,6,8,9,10,25$ などの倍数の判定法を出発点とし、任意の正の整数 $N$ に対して、$N$ の倍数の判定をすることができないか、その一般化の方法を考えてゆきます。（全ての整数は $1$ の倍数なので、$N\geq2$ としましょう。）

このように、いくつかの具体例から一般的な法則を見出だすことは数学においてよく行われています。

具体例と一般化の行き来を自由自在に行えると、議論を行なっていても迷子になりにくくなるので、意識しておけると良いと思います。

（私は、地上の迷路の中を歩きながら、上空からの空撮カメラも同時に扱えるような感覚と捉えています。）

今回の目標は

「$31415926535897932$ は $108$ の倍数であるか」

という問について、具体的に割り算を実行することなく答えることです。

早速、考えてゆきましょう。

本記事は【倍数判定法シリーズ】の前編です。

後編はこちら「倍数の判定方法（後編）　〜桁数を着実に減らそう〜」をご覧ください。

倍数判定法の考え方
1. 基本的な倍数判定の復習
2. 何の倍数を判定すれば良いか
タイプ１の判定方法の一般化
タイプ２の判定方法の一般化
問の答え
最後に

倍数判定法の考え方

基本的な倍数判定の復習

冒頭に紹介した $2,3,4,5,6,8,9,10,25$ の倍数の判定方法について、これらをタイプ別に分類して復習したいと思います。

タイプ１：末尾の数を見る

\begin{align*}
\mbox{2 の倍数}&\ \colon\ \mbox{一の位が偶数}\\
\mbox{4 の倍数}&\ \colon\ \mbox{下二桁が 4 の倍数}\\
\mbox{5 の倍数}&\ \colon\ \mbox{一の位が 0 または 5}\\
\mbox{8 の倍数}&\ \colon\ \mbox{下三桁が 8 の倍数}\\
\mbox{25 の倍数}&\ \colon\ \mbox{下二桁が 25 の倍数}
\end{align*}

タイプ２：各位の数を見る

\begin{align*}
\mbox{3 の倍数}&\ \colon\ \mbox{各位の数の和が 3 の倍数}\\
\mbox{9 の倍数}&\ \colon\ \mbox{各位の数の和が 9 の倍数}
\end{align*}

タイプ３：その他

\begin{align*}
\mbox{6 の倍数}&\ \colon\ \mbox{2 の倍数かつ 3 の倍数}\\
\mbox{10 の倍数}&\ \colon\ \mbox{2 の倍数かつ 5 の倍数}
\end{align*}

何の倍数を判定すれば良いか

上記の３タイプを眺めてみると、十進法によって表された各々の位の数が重要であることがわかりますね。

この「$10$」という数は $10=2\times5$ と素因数分解できるわけですが、タイプ１は $2$ の累乗か $5$ の累乗に関する判定法であることがわかります。

ここで、互いに素な正の整数 $a$, $b$ について、

「$ab$ の倍数」$\Longleftrightarrow$「$a$ の倍数かつ $b$ の倍数」

が成り立つので、倍数の判定法については互いに素であるものを考えれば十分であることがわかります。

$2$ 以上の整数 $N$ は一意的に素因数分解することが可能ですから、互いに素な整数の積に可能な限り分解すると、その構成要素は素数の累乗 $p^n$ の形をしています。

つまり、$p^n$ の倍数の判定法を与えることができれば、その組み合わせで任意の $N$ の倍数の判定法が得られるのです。

先ほど、タイプ１は $2$ の累乗か $5$ の累乗に関する判定法であると述べましたが、タイプ２が $2$ でも $5$ でもない素数の累乗に関する判定法であって、タイプ３がタイプ１と２の組み合わせで書ける（すなわち、複数の素因数を持つ）$N$ に関する判定法になります。

タイプ１とタイプ２の判定方法が明らかになれば、タイプ３のものは素因数分解することで直ちに従うので、タイプ１とタイプ２の判定方法について一般化の方法を考えます。

タイプ１の判定方法の一般化

$2$ の倍数や $5$ の倍数は下一桁を、$4=2^2$ の倍数や $25=5^2$ の倍数は下二桁を、$8=2^3$ の倍数は下三桁を見ていました。

これは、

$10$ が $2$ や $5$ の倍数なので十の位から上の位の数は $2$ や $5$ の倍数の判定に無関係であること
$100$ が $4$ や $25$ の倍数なので百の位から上の位の数は $4$ や $25$ の倍数の判定に無関係であること
$1000$ が $8$ の倍数なので千の位から上の位の数は $8$ の倍数の判定に無関係であること

に因ります。

そこで、正の整数 $M$ の下 $n$ 桁を $R$ として、$10^n$ の位から上の位を順に $a_n$, $a_{n+1}$, $\cdots$, $a_m$（但し、$m\geq n$）とおきます。このとき、
\begin{align*}
M
&=a_m\times10^m+\cdots+a_n\times10^n+R\\
&=(a_m\times10^{m-n}+\cdots+a_n)\times10^n+R\\
&=(a_m\times10^{m-n}+\cdots+a_n)\times2^n\times5^n+R
\end{align*}となるので、$M-R$ は $2^n$ の倍数及び $5^n$ の倍数となります。つまり、
$$
M\equiv R \pmod{2^n\ \mbox{及び}\ 5^n}
$$であるので、「元の数である $M$ は $2^n$ や $5^n$ を法として下 $n$ 桁である $R$ と合同となる」ことがわかります。

よって、$2^n$ の倍数や $5^n$ の倍数の判定を行うためには、

「下 $n$ 桁が $2^n$ の倍数や $5^n$ の倍数であること」

を判定すれば良いです。

この方法の良いところは、倍数の判定だけでなく、余りまで完全に判別できるところにあります。

例えば、$299792458$ を $4$ で割った余りを求めるときには、下二桁だけに着目して、求める余りは $58\div4$ の余りである $2$ に等しくなるのです。

タイプ２の判定方法の一般化

考察（オイラーの定理の活用）

このタイプの例として見た $3$ の倍数と $9$ の倍数について、その証明を追うことで考察をしてゆこうと思います。

正の整数 $M$ について、$10^n$ の位を $a_n$ とします。

$3$ や $9$ を法とすると $10$ は $1$ と合同なので
\begin{align*}
M
&=a_m\times10^m+\cdots+a_1\times10+a_0\\
&\equiv a_m\times1^m+\cdots+a_1\times1+a_0\\
&=a_m+\cdots+a_1+a_0
\end{align*}となるので、「元の数である $M$ は $3$ や $9$ を法として各桁の数の和と合同となる」ことがわかります。

同様にして、$2$ でも $5$ でもない素数 $p$ について

「$10^k$ が $p^n$ を法として $1$ と合同ならば、
末尾から $k$ 桁ごとに区切った数の和が元の数の余りに一致する」

ことが示されます。

つまり、$p^n$ に対して
$$
10^k\equiv 1 \pmod{p^n}
$$となるような正の整数 $k$ を見つければ良いことが言えるのです。

今、$10$ は法である $p^n$ と互いに素ですので、フェルマーの小定理を拡張したオイラーの定理と呼ばれる定理を適用することができます。

これらの定理についてはこちらの記事「フェルマーの小定理を証明　〜入試でどう使う？〜」をご覧ください。

区切る桁数 $k$ の決定

オイラーの定理を簡単に復習しておきましょう。

正の整数 $N$ に対して、$N$ と互いに素である $N$ 以下の正の整数の個数を $\varphi(N)$ と書くことにする（つまり、$\varphi$ をオイラーのファイ関数とする）と、定理の主張は次のようになります。

$N$ と互いに素な整数 $a$ に対して、
$a^{\varphi(N)}\equiv 1 \pmod N$ となる。

ここで、$N=p^n$ かつ $a=10$ としましょう。

$p^n$ 以下の $p$ の倍数は $p^{n-1}$ 個なので
$$
\varphi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)
$$となります。

これより、区切る桁数として $k=p^{n-1}(p-1)$ を採用することができますね。

例えば、$3$ の倍数については $\varphi(3)=3-1=2$ ですから、$2$ 桁ごとの和をとることになります。

また、$9$ の倍数については $\varphi(9)=3(3-1)=6$ ですから、$6$ 桁ごとの和をとることになります。

しかし実際には、共に $1$ 桁ごとの和を計算すれば良いわけです。

これより、一般的に最良の $k$ としては、$\varphi(p^n)$ すなわち $p^{n-1}(p-1)$ の正の約数の中から最小のものが選べることがわかります。

以上をまとめると

「$p^{n-1}(p-1)$ の正の約数の中から
$10^k\equiv 1$ なる $k$ を見つけ出し、
末尾から $k$ 桁ごとの和の余りを求めれば良い。」

となります。

区切る桁数 $k$ が偶数の場合

例えば、$11$ の倍数の判定条件を考えてみましょう。

$N=11$ ですから、$\varphi(11)=11-1=10$ の正の約数 $k$ の中から $10^k\equiv 1$ となる $k$ を見つけ出す必要があります。

ここで、$k=2$ とすると $10^k=10^2=100\equiv 1$ となります。

よって、$2$ 桁ごとの和の余りを求めれば $11$ の倍数の判定ができることになりますね。

さらに $k$ を小さく $k=1$ としてみましょう。

そうすると、$10^k=10^1=10\equiv -1$ となります。

よって、考察のときと同様に正の整数 $M$ の $10^n$ の位を $a_n$ とすると、$11$ を法として
\begin{align*}
M
&=a_n\times10^n+\cdots+a_1\times10+a_0\\
&\equiv a_n\times(-1)^n+\cdots-a_1+a_0
\end{align*}となります。

これより、$M$ は $1$ 桁ごとの交代和と合同になります。

こちらの方が区切る桁数が少なくなり、扱う数が小さくなり計算が楽ですね。

以上をまとめると

「$p^{n-1}(p-1)$ の正の約数の中から
$10^k\equiv \pm1$ なる $k$ を見つけ出し、
$10^k\equiv 1$ ならば末尾から $k$ 桁ごとの和の余りを
$10^k\equiv -1$ ならば末尾から $k$ 桁ごとの交代和の余りを
求めれば良い。」

となります。

この方法でも倍数の判定だけでなく、余りまで完全に判別できます。

問の答え

さて、冒頭で述べた「$31415926535897932$ は $108$ の倍数であるか」という問に答えましょう。

$108=2^2\times3^3$ であるのでこれはタイプ３です。

素因数分解の結果より、タイプ１の $4$ の倍数の判定とタイプ２の $27$ の倍数の判定を行えば良いです。

まずタイプ１。

下二桁である $32$ は $4$ の倍数なので、元の数も $4$ の倍数です。

次にタイプ２。

$\varphi(27)=\varphi(3^3)=3^2(3-1)=18$ なので、$18$ の正の約数を小さい順に調べると、$10^3\equiv 1\pmod{27}$ となります。

よって、末尾から $3$ 桁ごとの和を調べれば良いことがわかりますので、$27$ を法とすると
\begin{align*}
&31415926535897932\\
&\quad\equiv 31+415+926+535+897+932\\
&\quad\equiv 4+10+8-5+6-13\\
&\quad= 10
\end{align*}となります。

これより、元の数は $27$ の倍数ではありません。

以上より、

「$31415926535897932$ は $108$ の倍数ではない」

という結論を得ます。

「では、余りはいくつでしょうか？」

それは、連立合同式
$$
\begin{cases}
x\equiv0&\pmod{4}\\
x\equiv10&\pmod{27}
\end{cases}
$$を $0\leq x<108$ の範囲で解けば良いですね。

連立合同式については別の記事で解説しようと思います。

実際に解いてみると、$27$ で割って $10$ 余る数 $x$ であって $0\leq x<108$ の範囲にあるものは $10, 37, 64, 91$ です。

その中で $4$ の倍数であるものは $64$ であるので、求める余りは $64$ となります。

最後に

今回は、各位の数を用いた倍数の判定方法を見てきました。

我々が得た判定方法では余りまでわかるというメリットがある一方、$p^{n-1}(p-1)$ の正の約数 $k$ であって、$10^k\equiv\pm1 \pmod {p^n}$ となる “現実的な” $k$ を見出すのが一般には困難です。

例えば、$N=7^2=49$ を法としてみると $\varphi(N)=7(7-1)=42$ ですが、この正の約数 $k$ であって $10^k\equiv\pm1 \pmod{49}$ となる $k$ は $42$ しか存在しません。

よって、$42$ 桁を超えないとこの判定方法は有効ではありませんし、有効な場合でも $42$ 桁の数を $49$ で割らないといけないのです。

以上を踏まえて、ふたつの課題を述べて本記事を終えたいと思います。

今回は我々が普段用いる十進法で議論したが、他の表記法（例えば二進法や三進法、四進法など）では同様の判定方法が通用するか？通用させるには何を修正すれば良いか？
今回の判定方法のデメリットである「$k$ を見定めるのが困難である」「見つかった $k$ が大きいと嬉しくない」という点を克服できないか？倍数の判定に焦点を当てて、「余りまでわかる」というメリットを捨ててでも現実的な方法はないか？

ふたつめの課題については後編でひとつの答えを提案したいと思います。

是非、ご自身でも考えてみてくださいね。

AkiyaMath