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

ll N,A,X,Y;
int main(){
	fin >> A >> N;
	gcd(X,Y,A,N);
	while(X <= 0) X=N+X%N;
	fout << X;
}