受験生に教える用にまとめてみます。この記事で紹介するものは示せと言われない限りは基本的に既知として考えてよいと思っています。
おさえておきたい事実
最初におさえておきたい事実を 2 つ紹介します。まずはここから話を広げてみましょう。
1. a, b の公約数の集合は、 a-b, b の公約数の集合と一致する
ユークリッドの互除法などの元になっている考え方ですね。
整数 $a, b$ について、 $a, b$ の公約数は $a-b, b$ の公約数であり、逆に $a-b, b$ の公約数は $a, 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. ユークリッドの互除法の原理的な話
上の話をさらに広げてみます。
整数 \(a, b\) （\(a \geq b\)）の最大公約数を \(gcd (a, b)\) とする。
\(a\) を \(b\) で割った余りを \(r\) とするとき、次の式が成立する。
$$gcd(a, b) = gcd(b, r)$$
1の事実から、次の式が成り立つことがわかる。
gcd(a, b) = gcd(a-b, b)
\end{align*}
これを繰り返し用いると、次のことが言える。
gcd(a, b) = gcd(a-b, b) = … = gcd(a-kb, b)
\end{align*}
つまり \(a\) を \(b\) で割った商、余りをそれぞれ \(k, r\) とすれば、\(a = kb + r\) より \(gcd(a-kb, b) = gcd(r, b)\) つまり上の式が言える。
Point. どんな 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, b$ が互いに素ならば、$ax + by = 1$ をみたす整数 $x, y$ が存在する。
略証
\(a \geq b\)、 \(a, b\) は互いに素であるとする。 \(a\) を \(b\) で割った商と余りを \(q, r\) とすれば、\(a = bq + r\) が成立。このことから、
& ax + by = 1 \\
& \Leftrightarrow (bq + r) x + by = 1 \\
& \Leftrightarrow b(qx + y) + rx = 1
\end{align*}
と変形できる。つまり、 \(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\) の存在は上で既に示してある）として、
gcd(a, b) = gcd(b, r_1) = … = gcd(r_{i-1}, r_i) = gcd(r_{i-1}, 0) = r_{i-1}
\end{align*}
となるが、 \(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, c$ を整数として、 $a, b$ が互いに素であるとする。このとき、 $ac$ が $b$ の倍数であるならば、$c$ は $b$ の倍数である。
- \(a, b\) が互いに素
- \(ac\) が \(b\) の倍数
の 2 条件が成り立つとき、
- \(c\) が \(b\) の倍数
といえるわけですね。
略証
\(a, b\) は互いに素なので、 \(ax + by = 1\) となる \(x, y\) が存在する。このような \(x, y\) について、上の等式の両辺を \(c\) 倍すると \(acx + bcy = c\) となる。
\(ac\) は \(b\) の倍数だから、左辺 \(acx + bcy\) は \(b\) の倍数。よって \(c\) も \(b\) の倍数。 （証明終）
素数の基本的な性質
$p$ を素数、$a, b$ を整数とする。このとき、 「 $ab$ が $p$ の倍数」ならば、「 $a$ は $p$ の倍数」または 「 $b$ は $p$ の倍数」が成立する。
略証
\(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\) の倍数になる。（証明終）
これは一般の場合にも拡張できる。つまり、
$p$ を素数、$a_1, a_2, \ldots, a_n$ を整数とする。このとき、 「 $a_1 a_2 \cdots a_n$ が $p$ の倍数」ならば、「 $a_1$ は $p$ の倍数」または 「 $a_2$ は $p$ の倍数」または … 「$a_n$ は $p$ の倍数」が成立する。
おわり。