#include <bits/stdc++.h>

using namespace std;
ifstream in  ("inversmodular.in");
ofstream out("inversmodular.out");

void euclid_ceva(int a,int b,int &x, int &y){
	if(b==0){
		x=1;
	    y=0;
	}
	else{
		euclid_ceva(b,a%b,x,y);
		int aux=x;
		x=y;
		y=aux-y*(a/b);
	}
}


int main(){
	int a,b,x,y;
    in>>a>>b;

	euclid_ceva(a,b,x,y);
    if(x<=0){
		x=b+x%b;
    }

	out<<x;
}