#include<stdio.h>

long long a,n,inv,ins;

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

}


int main(){
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);

scanf("%lld %lld",&a,&n);


invers(inv,ins,a,n);
if(inv <= 0)
	inv = n + inv%n;

printf("%lld",inv);

return 0;}