#include <iostream>
#include <fstream>
using namespace std;

typedef long long ll;

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

ll gcd(ll a,ll b,ll& x,ll& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	} else {
		ll x0,y0;
		gcd(b,a%b,x0,y0);
		x = y0;
		y = x0 - y0 * (a/b);
	}
}

int main() {
	ll A,N,x,y;
	
	fin >> A >> N;
	
	gcd(A,N,x,y);
	
	if (x <= 0) {
		x = N + x % N;
	}
	
	fout << x << "\n";
	
	fin.close();
	fout.close();
	return 0;
}