算数や数学においても重要項目である「倍数の判定方法」ですが、教科書や参考書で扱われるような \(2,3,4,5,6,8,9,10,25\) などの倍数の判定法は通常、十進法によって表記された各位の数を用いたものが紹介されます。
例えば、
- \(3\) の倍数は各位の数の和が \(3\) の倍数
- \(4\) の倍数は下二桁が \(4\) の倍数
などです。
教科書で紹介される程度のものでは問題ないのですが、一般には
- 各位の数の和をとるときの区切る桁数
- 末尾の数で判定するときに考える桁数
が大きくなることがあり、常に実用的であるかというとそうでもないのです。
そこで本記事では、多少泥臭くても良いし、余りがわからなくても倍数の判定さえできれば良いから、とにかく現実的な判定方法がないか考えます。
そして、今回の目標は
「\(31415926535\) は \(1085\) の倍数であるか」
という問について、具体的に割り算を実行することなく答えることです。
早速、考えてゆきましょう。
本記事は【倍数判定法シリーズ】の後編です。
前編はこちら「倍数の判定方法（前編） 〜オイラーの定理で証明〜」をご覧ください。
桁数をコツコツ減らせないか考える
一の位を削り取ってみる
正の整数 \(M\) が正の整数 \(N\) の倍数であるかどうかを判定したいと思います。
\(M\) の桁数を減らしてゆきたいのですが
- 最高位の数を取り除いて計算するか
- 一の位の数を取り除いて計算するか
が自然に考えられますが、最高位の位は \(M\) のとり方に依存しており、その都度見定めなくてはなりません。
一方、一の位は如何なる \(M\) に対しても変わらず存在します。
これより、今回は一の位を取り除く方針で考えてゆきたいと思います。
正の整数 \(M\) の一の位を \(a\) とすると、非負整数 \(A\) を用いて
$$
M=10A+a
$$と書くことができます。
例えば、\(M=12345\) の場合、\(a=5\), \(A=1234\) であって、\(M=1234\times10+5\) となります。
\(N\) の倍数であるための必要条件
仮に \(M\) が \(N\) の倍数であるならば、整数 \(q\) を用いて \(M=qN\) と書くことができます。
よって、
\begin{align*}
M&=qN\\
10A+a&=qN\\
a&=qN-10A
\end{align*}という関係式が得られます。
さて、\(M\) は桁数の大きな正の整数を想定していますので、例えば、一の位を取り除いた \(A\) から一の位である \(a\) の \(l\) 倍を引いてみます。
\(M\) が \(N\) の倍数ならば、先ほどの関係式より
\begin{align*}
A-al
&=A-(qN-10A)l\\
&=(10l+1)A-lqN
\end{align*}となります。
これより、「\(10l+1\) が \(N\) の倍数になるように \(l\) を定めることができれば」\(A-al\) は \(N\) の倍数となるのです。
つまり、この \(l\) が存在する場合は
「\(M\) が \(N\) の倍数」\(\Longrightarrow\)「\(A-al\) が \(N\) の倍数」
となるのです。
\(N\) の倍数であるための十分条件
\(M\) を \(N\) で割った商を \(q\)、余りを \(r\) として \(M=qN+r\) と書きます。
このとき、先ほどと同様に
\begin{align*}
M&=qN+r\\
10A+a&=qN+r\\
a&=qN+r-10A
\end{align*}という関係式が得られます。
さて、「\(10l+1\) が \(N\) の倍数になるように \(l\) を定めることができた」としましょう。
このとき、先ほどの関係式より
\begin{align*}
A-al
&=A-(qN+r-10A)l\\
&=(10l+1)A-lqN-lr
\end{align*}となります。
ここで、我々は
「\(M\) が \(N\) の倍数」\(\Longleftarrow\)「\(A-al\) が \(N\) の倍数」
が成り立って欲しいという気持ちでいます。
\(A-al\) が \(N\) の倍数であるならば \(lr\) は \(N\) の倍数になるわけですが、我々が望んでいるのはより強い \(r=0\) という結論です。
\(10l+1\) は \(N\) の倍数ですから、\(l\) と \(N\) は互いに素です。
さらに、\(lr\) は \(N\) の倍数であるので、\(r\) が \(N\) の倍数にならなくてはなりません。
一方、\(r=0,1,\cdots,N-1\) であったので \(r=0\) しかあり得ません。
これより、\(M\) は \(N\) の倍数となりました。
\(N\) の倍数を判定できる \(N\) の条件
以上の議論より、
「\(10l+1\) が \(N\) の倍数になる整数 \(l\) が存在する」
という条件の下で、桁数を減らす判定方法
「\(M\) が \(N\) の倍数」\(\Longleftrightarrow\)「\(A-al\) が \(N\) の倍数」
を得ます。
さて、\(N\) が偶数の場合、\(10l+1\) は奇数なので \(N\) の倍数になることはあり得ませんね。
また、\(N\) が \(5\) の倍数の場合、\(10l+1\) は \(5\) の倍数ではないので \(N\) の倍数になることはあり得ません。
つまり、これらのときは上記の判定方法が使えません。
素直に、前編で紹介したように \(2^n\) や \(5^n\) の倍数は下 \(n\) 桁に着目することになりそうです。
一方、\(10\) と \(N\) が互いに素であるならば（例えば、ユークリッドの互除法により）
$$
10(-l)+qN=1
$$なる整数 \(l,q\) が存在します。
これより、\(10l+1=qN\) は無事に \(N\) の倍数となります。
つまり、このときは上記の判定方法が使えるということです。
以上より、\(2\) の倍数でも \(5\) の倍数でもない正の整数 \(N\) に対して
「\(M\) が \(N\) の倍数」\(\Longleftrightarrow\)「\(A-al\) が \(N\) の倍数」
という判定方法が適用できることがわかりました。
実際に練習してみよう！
例えば、\(1234567890\) は \(9\) の倍数であるか、という問題を考えてみます。
（各位の数の和は \(45\) で \(9\) の倍数なので、元の数も \(9\) の倍数であることはわかっています。）
\(10l+1\) が \(9\) の倍数になるような整数 \(l\) として、例えば \(l=-1\) がとれます。
よって、“一の位を取り除き、その一の位を足す’’ という操作を繰り返していけば良いです。
実際に計算してみると
\begin{align*}
&1234567890\\
\longrightarrow&\ 123456789+0=123456789\\
\longrightarrow&\ 12345678+9=12345687\\
\longrightarrow&\ 1234568+7=1234575\\
\longrightarrow&\ 123457+5=123462\\
\longrightarrow&\ 12346+2=12348\\
\longrightarrow&\ 1234+8=1242\\
\longrightarrow&\ 124+2=126\\
\longrightarrow&\ 12+6=18
\end{align*}となり、\(9\) の倍数であることがわかります。
最終的に \(9\) の倍数であるか否かが判断できるまで操作を繰り返します。
問の答え
さて、冒頭で述べた「\(31415926535\) は \(1085\) の倍数であるか」という問に答えましょう。
\(1085=5\times7\times31\) であるので、各々の素因数について倍数の判定を行います。
全ての倍数になっていれば、\(1085\) の倍数です。
まず、\(5\) の倍数であることは一の位から明らかですね。
次に、\(7\) について、\(10l+1\) が \(7\) の倍数になるような整数 \(l\) として、例えば \(l=2\) がとれます。
よって、“一の位を取り除き、その一の位の \(2\) 倍を引く’’ という操作を繰り返していけば良いです。
\begin{align*}
&31415926535\\
\longrightarrow&\ 3141592653-5\times2=3141592643\\
\longrightarrow&\ 314159264-3\times2=314159258\\
\longrightarrow&\ 31415925-8\times2=31415909\\
\longrightarrow&\ 3141590-9\times2=3141572\\
\longrightarrow&\ 314157-2\times2=314153\\
\longrightarrow&\ 31415-3\times2=31409\\
\longrightarrow&\ 3140-9\times2=3122\\
\longrightarrow&\ 312-2\times2=308\\
\longrightarrow&\ 30-8\times2=14
\end{align*}これより、\(7\) の倍数ですね。
最後に、\(31\) について、\(10l+1\) が \(31\) の倍数になるような整数 \(l\) として、例えば \(l=3\) がとれます。
よって、“一の位を取り除き、その一の位の \(3\) 倍を引く’’ という操作を繰り返していけば良いです。
\begin{align*}
&31415926535\\
\longrightarrow&\ 3141592653-5\times3=3141592638\\
\longrightarrow&\ 314159263-8\times3=314159239\\
\longrightarrow&\ 31415923-9\times3=31415896\\
\longrightarrow&\ 3141589-6\times3=3141571\\
\longrightarrow&\ 314157-1\times3=314154\\
\longrightarrow&\ 31415-4\times3=31403\\
\longrightarrow&\ 3140-3\times3=3131
\end{align*}これより、\(31\) の倍数ですね。
以上より、\(31415926535\) は \(1085\) の倍数であることがわかりました。
最後に
今回は、桁数を地道に減らしてゆく倍数の判定方法を見てきました。
前編の方法では区切る桁数が大きくなってしまうことがあるから、そのようなことが起こらない現実的な判定方法はないかと考えてきました。
その結果、確かに如何なる正の整数に対しても実行可能な判定方法が得られましたが、如何せん計算回数が多いです。
これは、試験などで用いる強力な判定法というよりは、倍数判定に関する試行錯誤、自由研究の結果と捉えるべきでしょう。
（しかし、この方法では一の位を取り除いて何倍かして引いてゆくわけなので、一の位が \(0\) の場合は何も考えずにどんどん取り除いて良いことになります。何倍しても \(0\) なので引いても数は不変ですから。よって、例えば部活動で \(19\) 万 \(8\) 千円の経費がかかったとすると、部員で等分できるかについて、この判定方法はいきなり \(198\) からスタートして良いのです。ですので、多少は役に立つかもしれません…。）
このシリーズの前編後編で見てきたように、倍数の判定方法を見出だすのに決まり切った方針はありません。
前編では基本的な倍数判定法をもとに一般化していく方法を、後編では桁数を減らしてゆく方法を考えてきました。
これらの他に、メリットを維持し、デメリットを改善したオリジナルの判定方法が見出だせるでしょうか。
是非、考えてみてくださいね。
コメント