整数に関する覚書

約数の性質

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

倍数判定法

`n` `n` の倍数判定方法
3
  • 各桁の数字を足した数が3の倍数になれば真
4
  • 1の位と10の位だけを見て、4の倍数なら真
  • 更にそこから 40 や 80 を引いた数で考えてもよい。
6
  • 2の倍数 且つ 3の倍数であれば真
7
  • 判定が難しい
  • 49(=7*7) と 91(=7*13) だけでも覚えておくと良い。
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コ と考えられる。

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

参考