gcd 計算と不定方程式

mygcd.html

 
function mygcd(a,b) {
  var r;
  r = a % b;
  while (r != 0) {
      a = b;
      b = r;
      r = a % b;
  }
  return b;
}
function mymain() {
  var a,b,g;
  a = parseInt(document.myform.aa.value);
  b = parseInt(document.myform.bb.value);
  g=mygcd(a,b);
}

入力部分の作り方は複利計算の場合と同じ.
実行してみる

mylineq.html

 
/* ax+by=1 専用 */
function zlin(a,b) {
  var r,q,sol;
  if (a==1) return [1,0];
  if (b == 0) {
    document.write("解がない.
");
    return [0,0];
  }
  r = a % b;
  q = Math.floor((a-r)/b);
  sol=zlin(b,r);
  document.write("b*x+r*y=1: ");
  document.write(b,"*(",sol[0],") + ", r,"*(",sol[1],") = 1 
");
  return [sol[1], sol[0]-q*sol[1]];
}
function mymain() {
  var a,b,g;
  a = parseInt(document.myform.aa.value);
  b = parseInt(document.myform.bb.value);
  g=zlin(a,b);
  document.write("[x,y]=",g,"
");
}

入力部分の作り方は複利計算の場合と同じ.
実行してみる

mylineq.py

参考: Python 版. google colaboratory

 
d=1;
def zlin(a,b):
  global d;
  if (b == 0):
    d=a;
    return [1,0];
  r = a % b;
  q = a//b;
  sol=zlin(b,r);
  print("b*x+r*y=",d,": ",end="");
  print(b,"*(",sol[0],") + ", r,"*(",sol[1],") = ",d);
  return [sol[1], sol[0]-q*sol[1]];


a=2232056097077077674161;
b=47244640421;
print(zlin(a,b));

a=2232056097077077674161;
b=47244640422;
print(zlin(a,b));

gcd 計算と不定方程式

mygcd.html

mylineq.html

mylineq.py

参考: 有限体の英語の講義