数学と人間の活動(整数の性質) 公式ページ

素因数分解の一般形

$$N = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$

正の約数の個数

$$(a_1+1)(a_2+1)\cdots(a_k+1)$$

2つの自然数の積と最大公約数・最小公倍数の関係

$$a \times b = G \times L$$

ユークリッドの互除法の性質

$$a = bq + r \ (0 \le r < b) \Longrightarrow \gcd(a, b) = \gcd(b, r)$$

1次不定方程式が整数解をもつための条件

$$ax+by=c \text{ が整数解をもつ} \iff \gcd(a,b) \text{ は } c \text{ を割り切る}$$

1次不定方程式の一般解

$$x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t \quad (d = \gcd(a,b),\ t \text{は整数})$$

n進法の位取りの公式

$$a_k \times n^k + a_{k-1} \times n^{k-1} + \cdots + a_1 \times n + a_0$$

2点を結ぶ線分上にある格子点の個数(両端を含む)

$$\gcd(|a|, |b|) + 1$$