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$$