kuhcrow/小ネタ/a*x+b*y=g の変更点 - 物理のかぎプロジェクトWiki

新規

編集

添付

変更点

トップ

最近の更新

ヘルプ

追加された行はこの色です。
削除された行はこの色です。
kuhcrow/小ネタ/a*x+b*y=g へ行く。
kuhcrow/小ネタ/a*x+b*y=g の差分を削除

 ** 小ネタ： ベズーの等式 a*x + b*y = gcd(a,b) [#ue42efa9]
 
 Joh さんの [[整域・整数の剰余類の環:http://hooktail.sub.jp/algebra/IntegralDomain/]] に
 
  d=ax+by                (1)
  このような x,y を探す問題はディオファントス方程式と呼ばれ，
  必ず解が一意的に決まることが知られていますが，ここでは解の存在証明は省略します(ゴメンナサイ (>_<))．
 
 とあったので、
 ここでは証明ぬきにいきなりこれを解くプログラムを作ってみました。
 
 - 任意の整数 a, b に対して、a * x + b * y = gcd(a,b) となる整数 x, y と、a,b の最大公約数 gcd(a,b) を求めます
 - 任意の整数 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