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

using namespace std;

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

int extended_euclid(int a,int b,ll &x,ll &y) {
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	int g = extended_euclid(b, a%b, x, y);
	int aux = y;
	y = x - (a/b) * y;
	x = aux;
	return g;
	
}

int main() {
	ll a, n;
	in >> a >> n;
	ll x, y;
	int g = extended_euclid(a, n, x, y);
	x = x % n;
	if( x < 0 ) x+= n;
	out << x << '\n';
	
	return 0;
}