査読

rst2hooktail

進行表

執筆中

かぎマニュ

物理のかぎプロジェクト

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• kuhcrow/小ネタ/a*x+b*y=g へ行く。
  • 1 (2014-10-25 (土) 14:26:33)
  • 2 (2014-10-25 (土) 14:29:24)
  • 3 (2014-10-25 (土) 16:54:08)

小ネタ： ベズーの等式 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) を求めます

• なおこの解は一意的でなく無数に存在します

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

プログラム bezout.html †

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

†