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