【倍数の判定法】
pは10と互いに素とする。
10x≡1 (mod p)の解を、x≡t (mod p)
a+tb≡0 (mod p)↔10a+b≡0 (mod p)
【例】7の倍数
10x≡1 (mod 7)
10x≡1+7×(-3)≡-20→x≡-2≡5
a-2b≡0 (mod 7)↔10a+b≡0 (mod 7)
a+5b≡0 (mod 7)↔10a+b≡0 (mod 7)
【例】13の倍数
10x≡1 (mod 13)
10x≡1+13×3≡40→x≡4
a+4b≡0 (mod 13)↔10a+b≡0 (mod 13)
【例】63の倍数
10x≡1 (mod 63)
10x≡1+63×3≡190→x≡19
a+19b≡0 (mod 63)
↔10a+b≡0 (mod 63)
【証明】
pと10は互いに素だから
ps+10t=1を満たす整数(s,t)が存在する
10a+b
=10a+(ps+10t)b=10(a+tb)+psb
よって、
a+tb≡0 (mod p)
↔10a+b≡0 (mod p)
tを考えると、10t≡1 (mod p)
tは、10x≡1 (mod p)の解である。
(2024/7/16)
【例】n=123456は7 の倍数か？
a+5b≡0 (mod 7)↔10a+b≡0 (mod 7)
12345+30=12375
1237+25=1262
126+10=136
13+30=43
n=123456は7の倍数でない。
(※)123456=7×17636+4
a-2b≡0 (mod 7)↔10a+b≡0 (mod 7)
を利用してもOK
【例】n=122667は31の倍数か？
10x≡1 (mod 31)
10x≡1-31≡-30→x≡-3
a-3b≡0 (mod 31)↔10a+b≡0 (mod 31)
12266-21=12245
1224-15=1209
120-27=93
9-9=0
n=122667は31の倍数である。
(※)122667=31×3957
【例】2021は43の倍数か？
10x≡1 (mod 43)
10x≡1+43×3≡130→x≡13≡-30
a+13b≡0↔10a+b≡0↔a-30b≡0
2021→202+13=215→21+65=86=43×2
2021→202-30=172→17-60=-43
2021は43 の倍数
(※)2021=43×47
計算が楽な方でやる。
