整数の性質の練習問題と解き方

素因数分解と約数・倍数

例：$72 = 2^3 \cdot 3^2$ の約数は $4 \times 3 = 12$ 個、総和は $15 \times 13 = 195$。最大公約数は共通な素因数を少ない方の指数で、最小公倍数はすべての素因数を多い方の指数で掛けて求めます。2 数 $a$, $b$ について $ab = (\text{最大公約数}) \times (\text{最小公倍数})$ が成り立ちます。

ユークリッドの互除法と一次不定方程式

$a = bq + r$ のとき、$a$ と $b$ の最大公約数は $b$ と $r$ の最大公約数に等しくなります。これを余りが 0 になるまで繰り返すのが互除法です。

一次不定方程式 $ax + by = c$（$a$, $b$ は互いに素）は、1 組の解 $(x_0,\ y_0)$ を見つけ、もとの式から引いて $a(x - x_0) = -b(y - y_0)$ とします。$a$ と $b$ は互いに素なので $x - x_0$ は $b$ の倍数で、

余りによる分類と n 進法

整数は 3 で割った余りで $3k$, $3k + 1$, $3k + 2$ に分類できます。この分類を使うと「$n^2$ を 3 で割った余りは 0 か 1」などが証明できます。合同式 $a \equiv b \pmod{m}$ を使うと、$2^{100}$ を 7 で割った余りのような計算も楽になります。