2個のナチュラルナンバー（自然数）たちでそのグレイテストコモンディバイザー（最大公約数）が1であるものたちに対して、何らか2個のインテジャー（整数）たちでインテジャー（整数）たち係数たちによるナチュラルナンバー（自然数）たちのリニアコンビネーション（線形結合）が1であるものがあることの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
ターゲットコンテキスト
- 読者は、任意の2個のナチュラルナンバー（自然数）たちでそのグレイテストコモンディバイザー（最大公約数）が1であるものたちに対して、何らか2個のインテジャー（整数）たちで当該インテジャー（整数）たち係数たちによる当該ナチュラルナンバー（自然数）たちのリニアコンビネーション（線形結合）が1であるものがあるという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(\mathbb{N}\):
\(n\): \(\in \mathbb{N}\)
\(n'\): \(\in \mathbb{N}\)で、\(n \le n'\)を満たすもの
//
ステートメント（言明）たち:
\(gcd (\{n, n'\}) = 1\)、ここで、\(gcd (\bullet)\)は引数のグレイテストコモンディバイザー（最大公約数）を表わす
\(\implies\)
\(\exists z, z' \in \mathbb{Z} (z n + z' n' = 1)\)
//
2: 証明
全体戦略: ステップ1: \(n = 0\)であるケースに対処する; ステップ2: \(n = 1\)であるケースに対処する; ステップ3: \(1 \lt n\)であるケースに対処する。
ステップ1:
\(n = 0\)であると仮定しよう。
\(gcd (\{n, n'\}) = 1\)は、\(n' = 1\)を意味する。
したがって、以下を満たす\(z = 0, z' = 1\)、つまり、\(z n + z' n' = 1\)、がある。
ステップ2:
\(n = 1\)であると仮定しよう。
\(n'\)は任意のものでよい。
しかし、いずれにせよ、以下を満たす\(z = 1, z' = 0\)、つまり、\(z n + z' n' = 1\)、がある（\(z = - (n' - 1), z' = 1\)も可能）。
ステップ3:
\(1 \lt n\)であると仮定しよう。
\(gcd (\{n, n'\}) = 1\)が意味するのは、\(n \lt n'\)なぜなら、もしも、\(n = n'\)である場合、\(gcd (\{n, n'\}) = n \neq 1\)。
したがって、\(1 \lt n \lt n'\)。
私たちは帰納的に考える、したがって、\(n_0 := n, n'_0 := n'\)としよう。
\(n'_0 - n_0 \in \mathbb{N} \setminus \{0\}\)を取ろう。
もしも、\(n'_0 - n_0 = 1\)である場合、完了である、なぜなら、\(-1 n_0 + 1 n'_0 = -1 n + 1 n' = 1\)。
そうでないと仮定しよう、それが意味するのは、\(1 \lt n_0, n'_0 - n_0 \lt n'_0\)。
\(n_0 \neq n'_0 - n_0\)、なぜなら、もしも、\(n_0 = n'_0 - n_0\)である場合、\(n'_0 = 2 n_0\)、それが意味するのは、\(n_0\)はあるコモンディバイザー（公約数）であった、ここで、\(1 \lt n_0\)、ということ、矛盾。
したがって、\(n_0 \lt n'_0 - n_0\)または\(n'_0 - n_0 \lt n_0\)。
\(gcd (\{n_0, n'_0 - n_0\}) = 1\)、任意の2個のナチュラルナンバー（自然数）たちに対して、当該ナンバー（数字）たちのコモンディバイザー（公約数）たちのセット（集合）は、大きくない方のナンバー（数）と当該ナンバー（数字）たちの非負差のコモンディバイザー（公約数）たちのセット（集合）であるという命題によって。
\(n_0 \lt n'_0 - n_0\)である時は、\(n_1 := n_0, n'_1 := n'_0 - n_0\)としよう; \(n'_0 - n_0 \lt n_0\)である時は、\(n_1 := n'_0 - n_0, n'_1 := n_0\)としよう。
すると、\(1 \lt n_1 \lt n'_1\)で\(gcd (\{n_1, n'_1\}) = 1\)、それが意味するのは、\(n_1, n'_1\)ペアは\(n_0, n'_0\)ペアに対する全ての要件たちを満たす、条件\(n'_1 \lt n'_0\)でもって、ということ。
したがって、\(n_1, n'_1\)ペアに対して私たちは\(n_0, n'_0\)ペアに対して行なわれたのと同じオペレーションを行ない、\(n'_1 - n_1 = 1\)に達するか、\(n_2, n'_2\)ペアを得る、条件\(n'_2 \lt n'_1\)でもって、等々と続く。
要点は、\(1 \lt n'_k \lt n'_{k - 1} \lt ... \lt n'_2 \lt n'_1 \lt n'_0\)であるから、当該反復は永遠に続くことはできないということ、それが意味するのは、\(n'_l - n_l = 1\)がある\(l \in \mathbb{N}\)に対して起こるということ。
しかし、\(n'_l - n_l = 1\)が意味するのは、何らかの\(z, z' \in \mathbb{Z}\)に対して\(z n + z' n' = 1\): \(n'_l - n_l\)は\(n_{l - 1}, n'_{l - 1}\)のインテジャー（整数）たちコエフィシェント（係数）たちリニアコンビネーション（線形結合）である、その一方、\(n_{l - 1}, n'_{l - 1}\)は\(n_{l - 2}, n'_{l - 2}\)のインテジャー（整数）たちコエフィシェント（係数）たちリニアコンビネーション（線形結合）である、それが意味するのは、\(n'_l - n_l\)は\(n_{l - 2}, n'_{l - 2}\)のインテジャー（整数）たちコエフィシェント（係数）たちリニアコンビネーション（線形結合）である、...、等々と続く、そして、\(n'_l - n_l\)は\(n_0 = n, n'_0 = n'\)のインテジャー（整数）たちコエフィシェント（係数）たちリニアコンビネーション（線形結合）である。
