kuhcrow/小ネタ/a*x+b*y=g のバックアップの現在との差分(No.2)

バックアップ一覧
差分を表示
ソースを表示
バックアップを表示
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) [#ue42efa9]
 
 Joh さんの [[整域・整数の剰余類の環:http://hooktail.sub.jp/algebra/IntegralDomain/]] に
 
 >d=ax+by                (1)~
 このような x,y を探す問題はディオファントス方程式と呼ばれ，~
 必ず解が一意的に決まることが知られていますが，~
 ここでは解の存在証明は省略します(ゴメンナサイ (>_<))．
  d=ax+by                (1)
  このような x,y を探す問題はディオファントス方程式と呼ばれ，
  必ず解が一意的に決まることが知られていますが，ここでは解の存在証明は省略します(ゴメンナサイ (>_<))．
 
 とあったので、
 ここでは証明ぬきにいきなりこれを解くプログラムを作ってみました。
 
 - なおこの解は一意的でなく無限に存在します
 - 任意の整数 a, b に対して、a * x + b * y = gcd(a,b) となる整数 x, y と a,b の最大公約数 gcd(a,b) を求めます
 
 - なお解となる x, y は一意的でなく無数に存在します
 
 - 上の式は特に [[ベズーの等式:http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity]]
 と呼ばれます
 というようです
 
 ** プログラム &ref(bezout.html); [#c448d1c2]
 
 - html + javascript 製です。最初は google spreadsheet で作ったけど「入力可だが保存不可」にできないみたいで‥
 - アルゴリズムはびっくりするくらい簡単です　（他のやり方もあると思います）
 
 --------
 *** [#g00e367e]
 
 #comment

物理のかぎプロジェクト