#include<fstream>
#include<iostream>
using namespace std;

int t,a,b,c;

void euclidext(int a,int b,int &x,int &y){
	if( b==0){
		x=1;
		y=0;
	}
	else{
		int x0,y0;
		euclidext(b, a % b,  x0, y0);
		x = y0;
		y = x0 - (a / b)*y0;
	}
}
int main(){
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>a>>b;
	
	int d,x,y;
	euclidext(a,b,x,y);
	while(x<0){
		x=x+b;
	}
	g<<x;
	
	
	return 0;
}