まず、標準ユークリッドアルゴリズムで527 と 341 の最大公約数をウォーミングアップとして求めましょう。
標準アルゴリズムは簡潔で分かりやすく、拡張アルゴリズムを実装するためのちょっとしたガイドとして役立つでしょう。
拡張ユークリッド アルゴリズムでは、3 番目の方程式 (青) を取り、両辺から 155(1) を引き、少し並べ替えて、31 が孤立する等価方程式を作成することにします。
次に、155を341-186（1）に置き換えると、それは155について2番目の方程式を解くことによって得られ、次のようになる。
さて、これをきれいにしましょう。 括弧の中に負の符号を分散させ、186 + 186 を 186-2 に置き換えることを確認してください。
気付いたかもしれませんが、標準アルゴリズムで逆算を行うだけなんですよ。 最終的な目標である 527 と 341 を含む方程式を得るには、このプロセスをもう 1 度実行する必要があります。
これを行うには、186 を 527 – 341(1) に置き換えます。これは 186 を解くと、最初の方程式になります。
再び2を分配して527と341のグループに結合して方程式を単純化する。
これで31を527と341の線形結合で表せましたね。 629>
さらに、線形の組み合わせの反対側の数字は最大公約数です。
拡張ユークリッド・アルゴリズムは、gcdを強調するだけでなく、ベゾウトの恒等式が得られるので便利です。
読んでくださってありがとうございました！
拡張ユークリッド・アルゴリズムは、ベゾウトの恒等式が得られるだけでなく、gcdを強調できるので便利です。