ベズーの等式もどき

言葉の誤用

ここ何回かの日記で出てきている「ベズーの等式」という言葉は、数学の詳しい人によると、用法が間違っていたみたい。本来のベズーの等式は右辺の値が、最大公約数でないといけない。クリ率実験で出てくるタイプの等式には特に名前が付いていないらしい。この日記では、とりあえず「ベズーの等式もどき」とでも呼んでおく。

解法

解法については、本当のベズーの等式でもベズーの等式もどきでも、ほとんど変わらない。プログラムで書いてみるとこんな感じ。

def gcdr(a,b,s,t,u,v)  
  return [a,s,t] if b==0
  q=a/b
  gcdr(b,a-q*b,u,v,s-q*u,t-q*v)
end

def gcd(a,b)
  gcdr(a,b,1,0,0,1)
end

# Find x, y such that a*x+b*y=c
def bezout(a,b,c)
  (d,n,m)=gcd(a,b)
  return nil unless c%d == 0
  k=c/d
  (x,y)=[k*n,k*m]
  (dx,dy) = [b/d, a/d]
  m=x/dx
  [x-m*dx, y+m*dy]
end