Nが2の倍数⇔一の位が偶数
Nが5の倍数⇔一の位が0か5
10a+bが7の倍数⇔a-2bが7の倍数
が知られている。
これを一般化しよう。
(※なぜ-2?、そんな素朴な疑問から)
【例】4865
486-2×5=476
47-2×6=35→7の倍数
よって、
476が7の倍数で、4865も7の倍数
4865=7×695
pと10が互いに素とする。
pの倍数かどうか判定する方法を考える。
pt+10n=1を満たす整数(t,n)が存在する。
n=-(pt-1)/10
10a+b=10a+(pt+10n)b=10(a+nb)+ptb
10a+bがpの倍数⇔a+nbがpの倍数
※|n|＞p/2のとき、m=n+pとする。
a+mb=a+nb+pb
a+nbがpの倍数⇔a+mbがpの倍数
7t+10n=1→(t,n)=(3,-2)→n=-2
よって、
10a+bが7の倍数⇔a-2bが7の倍数
もっと具体的に考えてみよう。
pの一の位に着目して、
1→t=1, 3→t=7, 7→t=3, 9→t=9
まとめると、
10とpは互いに素とする。
pの一の位1↔1,3↔7,9↔9でtを決める。
pt+10n=1→n=-(pt-1)/10
10a+bがpの倍数⇔a+nbはpの倍数
(※|n|＞p/2のときはn+pをnとしても可)
p=3→t=7→n=-(3×7-1)/10=-2
|-2|＞3/2より、n+p=-2+3=1
よって、
10a+bが3の倍数⇔a+bが3の倍数
もっと具体的に考察しよう。
①p=10k+1→t=1
n=-{(10k+1)×1-1}/10=-k
②p=10k+3→t=7
n=-{(10k+3)×7-1}/10=-7k-2
③p=10k-3→t=3
n=-{(10k-3)×3-1}/10=-3k+1
④p=10k-1 →t=9
n=-{(10k-1)×9-1}/10=-(90k-10)/10
=-9k+1→m=-9k+1+10k-1=k
すなわち、
①p=10k+1→n=-k
②p=10k+3→n=-7k-2→m=3k+1
③p=10k-3→n=-3k+1
④p=10k-1→n=-9k+1→m=k
※|n|＞p/2のとき、m=n+pとする。
10a+bがpの倍数⇔a+mbがpの倍数
【例】p=91→k=9→n=-9
10a+bが91の倍数⇔a-9bが91の倍数
4277→427-63=364→36-36=0
よって、4277は91の倍数
4277=91×47
【例】p=43→k=4→n=-28-2=-30→m=13
10a+bが43の倍数⇔a+13bが43の倍数
2021→202+13=215→21+65=86
よって、2021は43の倍数
2021=43×47
【例】p=7→k=1→n=-3×1+1=-2
10a+bが7の倍数⇔a-2bが7の倍数
1232→123-4=119→11-18=-7
よって、1232は7の倍数
1232=7×176
【例】p=19→k=2→m=2
10a+bが19の倍数⇔a+2bが19の倍数
532→53+4=57→5+14=19
よって、532は19の倍数
532=19×28
1234→123+8=131→13+2=15
よって、1234は19の倍数でない
1234=19×64+18
※割り切れるかどうかの判定であって、余りを求められる訳ではない。
最後に素数pの判定法をまとめると、
N=10a+b
p=3→a+bが3の倍数
p=7→a-2bが7の倍数
p=11→a-bが11の倍数
p=13→a+4bが13の倍数
p=17→a-5bが17の倍数
p=19→a+2bが19の倍数
p=23→a+7bが23の倍数
(2021/6/25)
【おまけ】
7×11×13=1001から、
3桁ごとに区切り、奇数番目の和と偶数番目の和の差を考える。
その差が7(11,13)の倍数なら元の数も7(11,13)の倍数である。
これと併用すると、
11,234,496
(11+496)-234=507-234=273
27-2×3=21→7の倍数
27-3=24→11の倍数でない
27+4×3=39→13の倍数
11234496=7×13×123456
