# 倍数判定
- 例えば、「整数$N$が$10x+y$で表せるとき、$N$が$7$の倍数ならば、$x-2y\equiv_70$」みたいなやつです。
:::spoiler 7の倍数判定の例
$126\to12-6*2=0$
$91\to9-1*2=7\to0$
$1008\to100-8*2=84\to8-4*2=0$
:::
- このような判別方法を、任意の正の整数$d$に対して作れるよう一般化

## 命題
$k,a,b,x,y\in\mathbb Z$
ただし、$a\perp b$であるとする。このとき、
$$N:=ak+b,X:=xk+y,D:=ay-bx$$
とおくと、任意の$N$の約数$d\in\mathbb N$に対して、
$$X\equiv_d0\Leftrightarrow D\equiv_d0$$
が成り立つ。

## 説明
- $k$は進数
- $d$は倍数かどうか判定したい数(上の例の7)
- $N$は倍数かどうか判定したい数の倍数(上の例の21)
- $X$は倍数かどうか判定される数(上の例の126,91,1008)
- $D$は判別式
- 上の命題は、判別式$D$が$d$で割り切れる場合かつそのときのみ$N$が$d$の倍数になることを表しています。

## 証明
### $X\equiv_d0\Rightarrow D\equiv_d0$
任意に$N$のや約数$d\in\mathbb N$をとると、
$$D=ay-bx\equiv_da(-xk)-(-ak)x=-kax+kax=0$$
が成り立つ。■
### $D\equiv_d0\Rightarrow X\equiv_d0$
任意に$N$のや約数$d\in\mathbb N$をとると、
$$aX=axk+ay\equiv_daxk+bx=(ak+b)x=Nx\equiv_d0$$
$$bX=bxk+by\equiv_dayk+by=(ak+b)y=Ny\equiv_d0$$
がわかる。ここで、$a\perp b$より、$ma+nb=1$をみたす$m,n\in \mathbb Z$がとれるので、
$$X=(ma+nb)X=m(aX)+n(bX)\equiv_d0$$
が成り立つ。■

:::spoiler 13の倍数の例
$a=9,b=1$を選択すると、
$28561\to2856-1*9=2847\to284-7*9=221\to22-1*9=13$
:::
:::spoiler 11の倍数の例
$a=10,b=-1$を選択すると、
$12441\to1244+10=1254\to125+40=165\to66$
:::