/*
ax=1(mod b)
ax%b=1
ax=kb+1
ax+kb=1
=======================
ax1+by1=gcd(a,b)
bx2+(a%b)y2=gcd(b,a%b)
(a,b)=(b,a%b)
ax1+by1=bx2+(a%b)y2
ax1+by1=bx2+(a-(a/b)*b)y2=bx2+ay2-(a/b)*by2=ay2+b(x2-(a/b)y2)
x1=y2
y1=x2-(a/b)y2
*/
#include<iostream>
#include<cstdio>
using namespace std;
int m,n;//(  mx=1(mod n)  mx%n=1  mx-ny=1)
void gcdplus(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return ;
	}
	gcdplus(b,a%b,x,y);
	int c=y;
	y=x-(a/b)*y;
	x=c;
	return ;
}
int main()
{
	//freopen("ddd.in","r",stdin);
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	cin>>m>>n;
	int x,y;
	gcdplus(m,n,x,y);
	if(x<0)//注意这里
	{
		x+=n;
	}
	cout<<x<<endl;
	return 0;
}