gcd(a、b、c)の係数を線形結合として見つけますか?

Aug 22 2020

与えられた数 $a,b,c\in\mathbb N$、 いう $k$ の最小の正の線形結合である $\{a,b,c\}$。今考えてみましょう$a$、次の場合:

$$ a=kq+r, 0\lt r\lt k, $$

次に、より小さな正の線形結合が存在します。 $\{a,b,c\}$、矛盾、そう $r=0$。のアイデア$b,c$ 同じです、私たちは得ます $k$ 分水界 $a,b,c$。しましょう$d=\gcd(a,b,c)$、以来 $d$ 分水界 $k$ そして $k\le d$$k=d$

そう $\gcd(a,b,c)$ の最小の正の線形結合として定義できます。 $\{a,b,c\}$、しかし、の係数を見つける方法 $a,b,c$ それぞれ?

回答

1 SiongThyeGoh Aug 22 2020 at 15:29

拡張ユークリッドアルゴリズムから、次のことがわかります。 $\alpha, \beta, \gamma, \delta$ そのようなtaht

$$gcd(a,b)=\alpha a + \beta b$$

$$gcd(a,b,c)=gcd(gcd(a,b), c)= \gamma c + \delta \gcd(a,b)$$

したがって、

$$\gcd(a,b,c) = \alpha \delta a + \beta \delta b + \gamma c$$