#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
void euclid(int a,int b,int &x,int &y)
{  
  if(b==0)
  { 
      x=1; 
      y=0; 
      return; 
      
  }
  int x0,y0,c=a/b;
  euclid(b,a%b,x0,y0);
  x=y0;
  y=x0-c*y0;
}
int main(){
	int a,n,x,y;
	cin>>a>>n;
	euclid(n,a,x,y);
	if (y<0)
	y=n-(-y)%n;
	cout<<y;
return 0;
}