#include <bits/stdc++.h>

using namespace std;

//#define IOS ios::sync_with_stdio(false), cin.tie(0);

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

#define int long long

void euclid(int a, int b, int &x, int &y)
{
	if(!b)
		x = 1, y = 0;
	else
	{ 
		euclid(b, a % b, x, y);
		int aux = x;
		x = y;
		y = aux - y * (a / b);
	}
}

main() 
{
	int a, n;
	fin >> a >> n;
	int a1, b1;
	euclid(a, n, a1, b1);
	if(a1 <= 0)
		a1 = (a1 + n) % n;
	fout << a1;
}