#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a, m;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

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);
	}
}

int main(){
	in >> a >> m;
	ll ans = 0, help;
	gcd(ans, help, a, m);
	if(ans <= 0) ans = m + ans%m;
	out << ans;
	return 0;
}