物理のかぎプロジェクト

メニュー

• トップ
• 物理のかぎプロジェクトについて
• メンバー情報
• 雑談用掲示板

• 査読
• rst2hooktail
• 執筆中
• かぎマニュアルズ
• メンバー専用
• 記事管理

• 間違い報告

• 物理のかぎしっぽ
• 掲示板

現在 5 名がオンラインです。

最新の25件

小ネタ： ベズーの等式 a*x + b*y = gcd(a,b) †

Joh さんの 整域・整数の剰余類の環 に

d=ax+by                (1)
このような x,y を探す問題はディオファントス方程式と呼ばれ，
必ず解が一意的に決まることが知られていますが，ここでは解の存在証明は省略します(ゴメンナサイ (>_<))．

とあったので、 ここでは証明ぬきにいきなりこれを解くプログラムを作ってみました。

• 任意の整数 a, b に対して、a * x + b * y = gcd(a,b) となる整数 x, y と a,b の最大公約数 gcd(a,b) を求めます

• なお解となる x, y は一意的でなく無数に存在します

• 上の式は特に ベズーの等式 というようです

プログラム bezout.html †

• html + javascript 製です。最初は google spreadsheet で作ったけど「入力可だが保存不可」にできないみたいで‥
• アルゴリズムはびっくりするくらい簡単です　（他のやり方もあると思います）

†