整数問題で使う基本的な性質などをまとめてみる（約数倍数、剰余まわり）

受験生に教える用にまとめてみます。この記事で紹介するものは示せと言われない限りは基本的に既知として考えてよいと思っています。

おさえておきたい事実

最初におさえておきたい事実を 2 つ紹介します。ここから話を広げてみましょう。

1. $a, b$ の公約数の集合は、$a-b, b$ の公約数の集合と一致する

ユークリッドの互除法などの元になっている考え方ですね。

集合が一致するので、最大公約数も一致する。

略証

• $S$ : $a, b$ の公約数の集合
• $T$ : $a-b, b$ の公約数の集合

とする。

任意の $s \in S$ に対して、$a, b$ は $s$ で割り切れるので、$a = sk, b = sl$ とかける。このとき $a-b = s(k-l)$ となるので $a-b$ も $s$ で割り切れる。よって $s$ は $a-b, b$ の公約数であるとも言えるので $s \in T$ が成立する。

よって $S \subseteq T$ が成立。

逆も同様に言えるので、 $T \subseteq S$ がいえ、結局 $S = T$ が成り立つ。（証明終）

2. ユークリッドの互除法の原理的なやつ

1の事実から、$gcd(a, b) = gcd(a-b, b)$ が成り立ちます。これを繰り返すと、$gcd(a, b) = gcd(a-b, b) = ... = gcd(a-kb, b)$ となります。

つまり $a$ を $b$ で割った商、余りをそれぞれ $k, r$ とすれば、$a = kb + r$ より $gcd(a-kb, b) = gcd(r, b)$ つまり上の式が言える。

ポイント: どんな2数の最大公約数でも求められる！

• $gcd(a, b) = gcd(b, r_1)$ : ただし $a$ を $b$ で割った余りを $r_1$ とする
• $gcd(b, r_1) = gcd(r_1, r_2)$ : ただし $b$ を $r_1$ で割った余りを $r_2$ とする
• ...

と繰り返し割り算をしていくと、あまりの定義からかならず $r_i = 0$ を満たす $i$ が存在することになる。（ $0 \leq r_1 < b$ , $0 \leq r_2 < r_1, ...$ と範囲が小さくなっていくので）

ということは、そのような最小の $i$ について、$gcd(a, b) = gcd(r_{i-1}, 0) = r_{i-1}$ を求めてやればこれが最大公約数になる。

整数論の基本定理

略証

$a \geq b$、 $a, b$ は互いに素であるとする。 $a$ を $b$ で割った商と余りを $q, r$ とすれば、$a = bq + r$ が成立。このことから、次のように変形できる。

つまり、 $bX + rY = 1$ なる整数 $X, Y$ が存在すれば、 $x = X, y = X - qY$ と対応付けることで、上式を満たす整数 $x, y$ を構築できたことになる。

以上の議論から、示すべき条件は次のように変形できる。

• $ax + by = 1$ をみたす整数 $x, y$ が存在
• $\Leftrightarrow bx + ry = 1$ をみたす整数 $x, y$ が存在

この操作を繰り返す。つまり、$r_i = 0$ （この $i$ の存在は上で既に示してある）として、

となるが、 $a, b$ は互いに素なので $gcd(a, b) = 1$ 。よって $r_{i-1} = 1$ とわかるので、結局示すべき条件は

• $ax + by = 1$ をみたす整数 $x, y$ が存在
• $\Leftrightarrow x + 0 \cdot y = 1$ をみたす整数 $x, y$ が存在

となり、これは真であるから条件が示された。（証明終）

整数の基本的な性質

ここから整数の基本的な性質、及び素数の基本的な性質を取り上げますが、たいていの問題はこの 2 つのどちらかの議論に帰着させて考えることができると思います。てことで定石というか、これは信頼できる事実だとして覚えておくとよさそう。

• $a, b$ が互いに素
• $ac$ が $b$ の倍数

のとき、

• $c$ は $b$ の倍数

といえます。

略証

$a, b$ は互いに素なので、 $ax + by = 1$ となる $x, y$ が存在する。このような $x, y$ について、上の等式の両辺を $c$ 倍すると $acx + bcy = c$ となる。

$ac$ は $b$ の倍数だから、左辺 $acx + bcy$ は $b$ の倍数。よって $c$ も $b$ の倍数。 （証明終）

素数の基本的な性質

これ、意外と意識しないとミスるんで気をつけてくださいね。$p$ が素数じゃないとだめです。$3 \times 4$ が $6$ の倍数でも、$3$ も $4$ も $6$ の倍数ではないですね。文字式になると本当にミスります。

略証

$a$ が $p$ の倍数ではないとき、 $b$ が $p$ の倍数になることを示す。

$a$ は $p$ の倍数ではないので、 $a$ と $p$ は互いに素。よって $ax + py = 1$ なる整数 $x, y$ が存在し、このような $x, y$ について、両辺を $b$ 倍すると $abx + pby = b$ となる。

$ab$ は $p$ の倍数であるから、左辺 $abx + pby$ は $p$ の倍数。よって $b$ は $p$ の倍数になる。（証明終）

また、これを2素数でなく一般まで拡張して

おわり。