#include<bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int &x, int &y){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b, a%b, y, x);
	y=y-a/b*x;
} 
int main(){
	int x,y;
	int p, a;
	cin>>a>>p;
	exgcd(a,p,x,y);
	x=(x%p+p)%p;
	cout<<x; 
}
 /*乘法求逆,通过扩展欧几里得进行实现
 就是说ax=1 通过ax+by=1去找*/ 

就是不知道y=y-a/b*x到底在干什么,写在这里能改动什么的值,纯属看不懂代码(原理我懂,就是ax+by=1,然后我们用 (r+bt)x+by=1去辗转)