Euler's Eyes
2022-07-10
最大公約数
発見をチェックしてください
ゼロ以外の最後の剰余は 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$ の間の約数の積部分には最大要素があり、次のようになります。
$$\mathcal{D}(a)\cap \mathcal{D}(b)\quad \Rightarrow \quad \text{tem um elemento máximo, para a e b natural.}$$最大と言えば、今日のトリビュートはプリンシペ・ド・テニスの跡部景吾です。以下はebay フィギュアです。跡部フィギュアのクレジットはファンサブ サイトです。
| 跡部景吾 | 私はマキシマムです |
|---|---|
|
|
最大公約数の定義
任意の (ゼロ以外の) 自然数の約数間の会合 (交差) に最大値がある場合。次に、次のように定義できます。
定義:
自然数 $a$ および $b$ が与えられると、null 以外 (ゼロ以外) になります。 $a$ と $b$ の約数の共通部分 (「会合」) の集合
$$\mathcal{D}(a)\cap \mathcal{D}(b)$$には最大要素があり、これを $a$ と $b$ の最大公約数と呼びます。
$$mdc(a, b) = \max \\{\mathcal{D}(a)\cap \mathcal{D}(b) \\}$$
最大公約数の例
自然数12と18がある場合、12と18の最大公約数は何ですか?
$$mdc(12,18) = ?$$| 自然数$(n)$ | $\mathcal{D}(n)$ | ディバイダー |
|---|---|---|
| 12 | $\mathcal{D}(12)$ | $ \\{ 1,2, 3, 4, 6, 12 \\} $ |
| 18 | $\mathcal{D}(18)$ | $ \\{ 1,2, 3, 6, 9, 18 \\} $ |
次のステップは、$12$ と $18$ の約数間の交差を確認することです。これから、次のことがわかります。
| $\mathcal{D}(12) \cap \mathcal{D}(18)$ | $mdc(12,18)$ |
|---|---|
| $ \\{ 1,2, 3, 6 \\} $ | $ \max \\{ 1,2, 3, 6 \\} = 6 $ |
したがって、$12$と$18$の最大公約数は$6$となります。
$$mdc(12, 18) = 6$$最大公約数のプロパティ
以下に最大公約数の性質を示します。
- ゼロ以外の 2 つの自然数 $a$ および $b$ については、次のことが有効です。 $$mdc(a,b) = mdc(b,a)$$
例：$a = 12$と$b = 18$の場合
$$mdc(12,18) = mdc(18,12)=6$$| $mdc(12,18)$ | $mdc(18,12)$ |
|---|---|
|
|
|
- ゼロ以外の自然数 $a$ $(a\neq 0)$ の $b$ の約数の場合、$mdc(a,b)=a$
たとえば、$a = 6$ と $b = 18,$ の場合、6 は 18 の約数であることに注意してください。このような：
$$mdc(6,18) = 6$$
- 任意の 2 つの非ゼロ自然数 $a$ および $b$ について、
したがって、$a$ と $b$ は素数です。
たとえば、$a = 2$ と $b = 3$ の場合は次のようになります。
$$mdc(2,3) = 1$$したがって、2 と 3 は素数です。
最大公約数の幾何学的例
最大公約数法を示すために、Euclid の方法を使用します。 $a$ と $b$ をゼロ以外の自然数とする。 $a=77$と$b=21$を仮定します。
この方法は、辺が自然数である正方形で長方形の領域を覆うことに基づいています。このように、$mdc(77,21) = 7$ を計算するだけで済みます。
幾何学的な方法で求めた77と21の最大公約数は次のようになります。
IMPA と MDC
- Impa ポータル: 最大公約数
- Impa ポータル: 最大公約数のプロパティ
これは最大公約数 (gcd) の概要です。次回は最小公倍数を紹介します。