#include<fstream>
#include<iostream>
using  namespace std;
int mygcd(int a,int b,int& x,int& y)
{
	if(b==0){
	    x = 1; y = 0;
        return a;
	}else{
	    int x0,y0, gc;
	    gc = mygcd(b , a%b , x0 , y0);
	    x = y0;
	    y = x0 - (a/b)*y0;
        return gc;
	}
}
int main()
{
	freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a,n,x,y;
    scanf("%d %d",&a,&n);
    int gc=mygcd(a,n,x,y);
    while( x<0 ) x += n;
    printf("%d\n",x%n);
	return 0;
}