最大公約数
ユークリッドと縮小問題
古代に書かれた『原論』の中で、ユークリッドは最大公約数を見つける手順を示しました。すべての約数をリストする代わりに、より小さな割り算と余りを扱うことができます。
あなたが調査する番です: 24 と 18 を調査します: 24 = 1 × 18 + 6; 18 = 3 × 6 + 0 となります。最後のゼロ以外の余りは何でしたか?授業中のスクエアエクスプローラーと比較してみましょう。
セント アンドリュース大学の MacTutor に関する史料を発見してください。
発見をチェックしてください ゼロ以外の最後の剰余は 6、つまり GCD でした。 6 辺を持つ正方形では、24 と 18 辺を持つ長方形を余分なく覆うこともできます。
素数の投稿では、約数セットについて説明しました。たとえば、自然数 $a$ が与えられた場合、自然数の約数のセットは次の式で与えられます。
$$\mathcal{D}(a) $$ ゼロ以外の数値 $a$ の場合。また、1 は常にセット $\mathcal{D}(a)$ に属し、$a$ も属していることがわかりました。
自然数の約数を求める したがって、数値 $a$ の約数の集合は有限です。言い換えれば、次のようになります。
$$1\in \mathcal{D}(a) = \\{1,\dots, a\\}$$ $$a\in \mathcal{D}(a) = \\{1,\dots, a\\}$$このように、任意の 2 つの自然数 $a$ と $b$ の間の約数の積部分には最大要素があり、次のようになります。
