ユークリッドの互除法について

質問

ユークリッドの互除法を用いて
a*e+b*Phi=1
となるようなa,bを求めるプログラムを作りたいのですが
以下のようにしても正しい値になりません
どこが間違っているのでしょうか？

e=53499289;
Phi=96298720;

d=0;
d_old=1;
Psi=1;
Psi_old=0;

for (;Phi!=0;){
a= e/Phi;

h=e;
e=Phi;
Phi= h%Phi;

h=d_old;
d_old=d;
d=h-d*a;

h=Psi_old;
Psi_old=Psi;
Psi=h-Psi*b;
}

if (e<0){
b=-e;
}else{
b=e;
}

printf ("(%d)*e+(%d)*Phi_n=%d\n", d_old,Psi_old,b);

正しくは
9*e+(-5)*Phi=1
となるはずです

回答No.2

php504 · ベストアンサー

変数がわかりにくかったので勝手に変えました

#include <stdio.h>
int main(void)
{
int q;
int n, n1, n2;
int a, a1, a2;
int b, b1, b2;

n = 53499289;
n1 = 96298720;
a = 1;
a1 = 0;
b = 0;
b1 = 1;
for (;n1 != 0;){
q = n / n1;
n2 = n % n1;
a2 = a - q*a1;
b2 = b - q*b1;
n = n1;
n1 = n2;
a = a1;
a1 = a2;
b = b1;
b1 = b2;
}
printf ("(%d)*x+(%d)*y=%d\n", a, b, n);
return 0;
}

お礼

Psi=h-Psi*bのbをaにすればよかったんですね

ありがとうございます

回答No.1

asuncion

コードを掲載するときは、断片ではなく
コンパイルできる形の全文を掲載してください。

> Psi=h-Psi*b;

bに何が入っているかわからない状態で
この文を実行している点に問題があります。

お礼

わかりました、気をつけます。

ありがとうございます