#include<bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
typedef long long int ll;
ll euclid(ll a,ll mod,ll &x,ll &y)
{
	if(mod==0)
	{
		x=1;
		y=0;
		return a;
	}
	else {
		ll p,q;
		int r=euclid(mod,a%mod,p,q);
		x=q;
		y=p-q*(a/mod);
		return r;
	}
}
int main()
{
	ll a,mod,aux,inv;
	fin>>a>>mod;
	ll i=euclid(a,mod,inv,aux);
	while(inv<=0) inv+=mod;
	fout<<inv;
}