整数に関する覚書

約数の性質

自然数 `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} \]

倍数判定法

7の倍数

9の倍数

各桁の数字の合計と合同(mod 9)であることを利用する。

11の倍数

各桁の数字を順番に足す引くした結果と合同(mod 11)であることを利用する。

9で割った余りを簡単に算出する

  1. 各桁の数字を足す。
  2. 2桁以上になったら、再度1を行う。
  3. 最終的に1桁になった数字が、最初の数字を9で割った余りになっている。

検算にも使える。

ユークリッドの互除法

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

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

\[ b = qa + r \]

このとき、

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

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

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

(参考:ユークリッドの互除法 - Wikipedia

参考