#include <stdio.h>

int gcd(int x,int y)
{
while (x!=y)
  if (x>y)
    x-=y;
  else
    y-=x;
return x;
}

void extendedEuclid(int u,int v,int *u3out,int *u1out,int *u2out)
// See Knuth, TAOCP, Vol 2, p. 342, Algorithm X
// u and v are input; u1out, u2out, u3out are output such that
// u•u1out + v•u2out = u3out = gcd(u,v)
{
int t[4],uArray[4],vArray[4];
int i,q;

uArray[1]=1;
uArray[2]=0;
uArray[3]=u;

vArray[1]=0;
vArray[2]=1;
vArray[3]=v;

while (vArray[3]!=0)
{
  q=uArray[3]/vArray[3];

  for (i=1;i<=3;i++)
    t[i]=uArray[i]-vArray[i]*q;

  for (i=1;i<=3;i++)
    uArray[i]=vArray[i];

  for (i=1;i<=3;i++)
    vArray[i]=t[i];
}

(*u1out)=uArray[1];
(*u2out)=uArray[2];
(*u3out)=uArray[3];
}

main()
{
int x,y,u1out,u2out,u3out;

scanf("%d %d",&x,&y);
while (x && y)
{
  printf("gcd of %d and %d is %d\n",x,y,gcd(x,y));
  extendedEuclid(x,y,&u3out,&u1out,&u2out);
  printf("%d•%d + %d•%d = %d = gcd(%d,%d)\n",
    x,u1out,y,u2out,u3out,x,y);
  scanf("%d %d",&x,&y);
}
}