整数に関する覚書

約数の性質

自然数 `N` を素因数分解した結果 `N = p^{α}q^{β}\cdotsr^{γ}` となる場合

1. `N` のすべての約数

\[ (1 + p + p^{2} + \cdots + p^{α} )(1 + q + q^{2} + \cdots + q^{β})\cdots (1 + r + r^{2} \cdots + r^{γ}) \tag{1} \]

を展開したときの各項となる。

2. `N` の約数の個数（`1` と `N` を含める）

\[ (α + 1)(β + 1) ... (γ + 1) \]

3. `N` のすべての約数の和

(1) に等しい。

以下とも等しい（等比数列の和）。

\[ \frac{p^{α+1}-1}{p-1} \cdot \frac{q^{β+1}-1}{q-1} \cdots \frac{r^{γ+1}-1}{r-1} \]

4. `N` のすべての約数の積

\[ N^{約数の個数/2} \]


`n`	`n` の倍数判定方法
3	各桁の数字を足した数が3の倍数になれば真
4	1の位と10の位だけを見て、4の倍数なら真更にそこから 40 や 80 を引いた数で考えてもよい。
6	2の倍数且つ 3の倍数であれば真
7	判定が難しい 49(=77) と 91(=713) だけでも覚えておくと良い。
8	1の位と10の位と100の位だけを見て、8の倍数なら真
9	各桁の数を足した数が9の倍数になれば真 (各桁の数字の合計と合同(mod 9)であることを利用している)
11	各桁の数字を順番に足す引くした数が、0 か 11 なら真 (各桁の数字を順番に足す引くした結果と合同(mod 11)であることを利用している) 100の位と1の位の数字を足すと 10の位の数字になれば真
12	3の倍数且つ 4の倍数であれば真
25	1の位と10の位だけが、00, 25, 50, 75 なら真更に25割った数を計算する場合、100の位の数字40コや 1000の位の数字400コと考えられる。

検算にも使える。

最大公約数(G.C.M.)を求める。

a, b は自然数で a ≠ 0 とする。 b を a で割った商を q、剰余を r とすると

\[ b = qa + r \]

このとき、

( `b` と `a` の公約数全体の集合 ) = ( `a` と `r` の公約数全体の集合 )

となる。当然 G.C.M も同じ。

次は `a` を `r` で割ると、また同じことが言える。この操作を繰り返す。