#include<stdio.h>
int exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;
y=;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-(a/b)*y;
return r;
}
int main(){
int n,m,x,y;
while(~scanf("%d%d",&m,&n)){
exgcd(m,n,x,y);
while(x<)
x+=n;
printf("%d\n",x);
}
}