その三 倍数判定の話

 小学生の時に教頭にそろばんを教わっていた事も私に数の世界を引き込む一因となった.
ある日,進級試験で会場へ向かう車の中で,ウォームアップのためか教頭が「今からすれ違う車のナンバーが3で割り切れるかどうかを見分けてみてはどうでしょう」というお題を出した.車のナンバーは4桁,暗算で割り算できなくもないだろうがそうしているうちに次の車がやってきてとても間に合わない.さてどうしたものか,というときに助け舟が出た.「各桁の和が3の倍数になれば,ナンバーも3の倍数ですよ」.これはいい事を聞いた.全部足し算するのならぱっと見ただけでできる.2145…○,7096…×,4883…×,といった具合に判定がすぐにできるようになった.
 慣れてくるとすべてを足さなくてもいい事に気付く.たとえば3468のとき,全部足して21だからOKなのだが千の位の3,十の位の6なんてもとから3の倍数なので計算の対象からはずしても構わないので4と8のみで○.さらに,0から9までを3で割った「あまり」の和でも構わないから3468→0102と変換,和が3となって3で割れる,としても良い.


 さて,3の倍数ばかり詳しくなっても仕方がない.他の数の倍数判定はどうしたら良いのだろう.(modについては合同式の話参照.)

2の倍数
これは10≡0 (mod 2)なので一の位が偶数ならOK.

3の倍数
上にも書いたが,各桁の和が3の倍数なら元の数も3の倍数.
簡単な証明をつけると,10n-1≡0 (mod 9)を利用してN=Σ(k=0〜n)Ak*10kでNの十進法表記を表すことにする(0≦Ak≦9)と,各Ak*10kに対してAk*10k≡Ak(mod 3)なのでN≡Σ(k=0〜n)An(mod 3)となるからだ.

4の倍数
100≡0 (mod 4)なので,下二桁が4の倍数ならOK.二桁の数字の4の倍数の見分け方は,
(ア)一の位が0,4,8なら十の位が偶数
(イ)一の位が2,6なら十の位が奇数

でOK.

5の倍数
10≡0 (mod 5)なので一の位が0または5ならOK.

6の倍数
6=2×3なので2の倍数であり,しかも3の倍数ならばOK.(これ以降,素数の累乗でない合成数は省くことにします.)

7の倍数
(ア)1001≡0 (mod 7)なので下からから3桁ずつ区切って,交互にプラス,マイナスとしていってそれが7の倍数ならばOK.
たとえば5764801なら,3桁ずつ区切って
5 764 801
交互にプラス,マイナスして
5-764+801=42
42は7の倍数なのでもとの5764801も7の倍数,というわけだ.
(イ)もとの数をN=10A+Bとする(0≦B≦9)とすると10A+B≡0 (mod 7)⇔A-2B≡0 (mod 7)を利用する(特に(ア)の例で3桁の数が残った場合).
前の5764801なら,1の位の「1」を取り去って2倍して残りから引く.
576480-1×2=576478
同様に
57647-8×2=57631
5763-1×2=5761
576-1×2=574
57-4×2=49

49まで減らせば7の倍数と分かるのでもとの5764801も7の倍数.
では(イ)の証明を.

10A+B≡0 (mod 7)
B≡-10A (mod 7)
2B≡-20A (mod 7)
A-2B≡21A≡0 (mod 7)

A-2B≡0 (mod 7)
A≡2B (mod 7)
10A≡20B (mod 7)
10A+B≡21B≡0 (mod 7).


8の倍数
1000≡0 (mod 8)なので下三桁が8の倍数ならばOK.三桁の数が8の倍数であるかどうかの判別は,
(ア)下二桁が8の倍数ならば百の位が偶数
(イ)下二桁が8の倍数でない4の倍数ならば百の位が奇数

でOK.

9の倍数
3の倍数と同じ.各桁の和が9の倍数になればOK.

11の倍数
(ア)100≡1 (mod 11)なので下から二桁ずつ区切り,その総和が11の倍数ならばOK.
たとえば214358881なら,
2 14 35 88 81
と分けて
2+14+35+88+81=220
220は11の倍数なのでもとの214358881も11の倍数だ.
(イ)10≡-1 (mod 11)なので,各桁を交互にプラス,マイナスしていってそれが11の倍数ならばOK.
前の214358881なら,
2 1 4 3 5 8 8 8 1
と分けて,
2-1+4-3+5-8+8-8+1=0
なので214358881は11の倍数.

13の倍数
(ア)1001≡0 (mod 13)なので7の倍数と同様に下から三桁ずつ区切って交互にプラス,マイナスしていってそれが13の倍数ならばOK.
たとえば4826809なら,
4 826 809
と分けて
4-826+809=-13
なので4826809は13の倍数だ.
(イ)3桁の数で見分けにくいときはN=10A+Bとする(0≦B≦9)と10A+B≡0 (mod 13)⇔A+4B≡0 (mod 13)を利用する(特に(ア)の例で3桁の数が残った場合).
たとえば4826809なら,
482680+9×4=482716
48271+6×4=48295
4829+5×4=4849
484+9×4=520
52+0×4=52
5+2×4=13

となるので4826809は13の倍数だ.あとは証明.

10A+B≡0 (mod 13)
B≡-10A (mod 13)
4B≡-40A (mod 13)
A+4B≡-39A≡0 (mod 13)

A+4B≡0 (mod 13)
A≡-4B (mod 13)
10A≡-40B (mod 13)
10A+B≡-39B≡0 (mod 13).



 ここまでで15までの数の倍数の判定ができるはず.しかし,こう書いてくると「割ったほうが早くないか?」と突っ込まれそうな感じだが…


戻る