📐 整数の性質の公式まとめ

「整数の性質」で学ぶ公式をまとめました。各公式をタップすると解説記事にジャンプします。

約数・倍数・素因数分解【最大公約数・最小公倍数】

1.1. 約数（因数）とは
$a \div b \text{ が整数} \Leftrightarrow b \mid a \quad (b \text{ は } a \text{ の約数})$
1.1. 約数（因数）とは
$12 \text{ の約数}: 1, 2, 3, 4, 6, 12$
2.2. 素因数分解
$360 = 2 \times 180 = 2 \times 2 \times 90 = 2^2 \times 2 \times 45 = 2^3 \times 45$
2.2. 素因数分解
$= 2^3 \times 3 \times 15 = 2^3 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5$
2.2. 素因数分解
$360 = 2^3 \times 3^2 \times 5$
2.3. 約数の個数の求め方
$\text{約数の個数} = (a+1)(b+1)(c+1) \cdots$
2.3. 約数の個数の求め方
$(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24 \text{ 個}$
3.2. 素因数分解を使った GCD の求め方
$360 = 2^3 \times 3^2 \times 5$
3.2. 素因数分解を使った GCD の求め方
$504 = 2^3 \times 3^2 \times 7$
3.2. 素因数分解を使った GCD の求め方
$\gcd(360, 504) = 2^3 \times 3^2 = 8 \times 9 = 72$
4.2. 素因数分解を使った LCM の求め方
$360 = 2^3 \times 3^2 \times 5^1$
4.2. 素因数分解を使った LCM の求め方
$504 = 2^3 \times 3^2 \times 7^1$
4.2. 素因数分解を使った LCM の求め方
$\text{lcm}(360, 504) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 8 \times 9 \times 5 \times 7 = 2520$
4.3. GCD と LCM の関係
$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$
5.1. 約数の総和の公式
$\text{約数の総和} = (1 + p + p^2 + \cdots + p^a)(1 + q + q^2 + \cdots + q^b)$
5.1. 約数の総和の公式
$= \frac{p^{a+1}-1}{p-1} \times \frac{q^{b+1}-1}{q-1}$
5.1. 約数の総和の公式
$(1 + 2 + 4)(1 + 3) = 7 \times 4 = 28$

最大公約数・最小公倍数とユークリッドの互除法の求め方

2. 最大公約数と最小公倍数の関係
$a \times b = g \times l$
3. ユークリッドの互除法とは
$\gcd(a, b) = \gcd(b, r) \quad (r \text{は } a \div b \text{ の余り})$

一次不定方程式とn進法【ディオファントス方程式・基数変換】

1.2. 解の存在条件
$ax + by = c \text{ が整数解をもつ} \Leftrightarrow \gcd(a, b) \mid c$
2.2. ステップ2：一般解を書く
$x = x_0 + \frac{b}{\gcd(a,b)} t, \quad y = y_0 - \frac{a}{\gcd(a,b)} t \quad (t \in \mathbb{Z})$
2.2. ステップ2：一般解を書く
$x = x_0 + bt, \quad y = y_0 - at \quad (t \in \mathbb{Z})$
4.2. n進法の位の値
$a_k \times n^k + a_{k-1} \times n^{k-1} + \cdots + a_1 \times n^1 + a_0 \times n^0$