ax+by=c,不定方程式(拡張ユークリッド)を解決する

まずいくつかの定理があります.私たちは知っていなければなりません.ここで私も一つ一つ証明します.
——————————————————————————————————————
定理1:gcd(a,b)=gcd(b,a%b);これはユークリッドが提出し証明したものです.(%は余を取るという意味で、数学では
modで表すことができる);
以下は証明プロセスです
——————————————————————————————————————
a=k*b+r;(kは整数);=>r = a%b;
dをa,bのいずれかの公約数とする.=>d|a,d|b(d|aの意味はdがaによって除去されることを意味する);
またr=k*b-a=>d|(k*b-a);
以上、d|b,d|(a%b)=>dはb,a%bの公約数である.
以上のdはa,bの公約数であり、b,a%bの公約数でもある.
以上、gcd(a,b)==gcd(b,a%b)を得ることができる.
証明が終わる
——————————————————————————————————————
定理2:a*x+b*y=gcd(a,b)には必ず解が存在する.この定理はペ蜀定理、あるいは貝祖定理とも呼ばれている.
以下に、プロセスを証明します.
——————————————————————————————————————
今はまだ...
——————————————————————————————————————
以下はa*x+b*y==gcd(a,b)を解く過程である.
——————————————————————————————————————
b=0のとき、a*x==gcd(a,0)==a;  =>x=1,y=0;
a>b>0の場合:
定理1からgcd(a,b)==gcd(b,a%b)を得る.
容易得a*X 1+b*Y 1==b*X 2+(a%b)*Y 2;
=> a*X1 + b*Y1 == b * X2 +(a-[a/b] * b) * Y2;(ここでの/は残除法を持たない、すなわちc++の中の/);
=> a*X1 + b*Y1 == a * Y2 + b * (X2 - [a/b] * y2);
以上得ることができる.X1 == Y2;
               2.Y1 == X2 - [a/b] * y2;
明らかに以上の2つの方程式はずっと再帰することができる.
b=0に再帰すると,Xn=1,Yn=0を求めることができる.そして私たちはずっと遡って求めることができます
X1,Y1;
コードは次のとおりです.

#include
int exgcd(int a, int b, int &x, int &y);
int main()
{
	
	int a, b, x = 0, y = 0;
	
	scanf("%d %d",&a, &b);
	
	int gcd = exgcd(a,b,x,y);
	
	printf("%d %d %d
", gcd, x, y);
	
	
	return 0;
} 

int exgcd(int a, int b, int &x, int &y)
{
	
	if(b>a)
	return exgcd( b,  a,  y,  x);
	
	if(b==0)
	{
		x = 1, y = 0;
		return a;
	}
	int r=exgcd(b, a%b, x, y);
	
	int temp = x;
	
	x = y;
	
	y = temp - (a/b) * y;
	
	return r;
	
}

以上はa*x+b*y==gcd(a,b)のある1組の特解X 1,Y 1を求める過程である
従ってa*x+b*y==gcd(a,b)の通解はX=X 1−b/gcd(a,b)*tである
Y=Y 1+a/gcd(a,b)*tは任意の整数である.
——————————————————————————————————————
以下にax+by=cを求める過程を示す.良い表現のために,前のステップのax+by==gcd(a,b)を
 am + bn == gcd(a,b).
——————————————————————————————————————
c%gcd(a,b)==0のときに解があり、k*gcd(a,b)==cとなる.
=> k*a*m + k*b*n == k*gcd(a,b);
=>x == k*m == c*m/gcd(a,b)  ,  y == k*n == c*n/gcd(a,b) ;
X 0,Y 0をa*x+byのいずれかの特解とする.この不定方程式の通解は
X = X0 - b/gcd(a,b)*t;
Y = Y0 + a/gcd(a,b)*t;tは任意の整数である
X = (c*M0 - b*t)/gcd(a,b);
Y = (c*N0 + a*t)/gcd(a,b);
——————————————————————————————————————
以上、不定方程式a*x+b*y==cを解く手順は
1.拡張ユークリッドを用いてa*m+b*y=gcd(a,b)の一連の特解M 0,N 0を求める.
2.a*x+b*y=cの通解をX=(c*M 0-b*t)/gcd(a,b)と求める.
                                                     Y = (c*N0 + a*t)/gcd(a,b);