#include <fstream>
#include <iostream>
#define MAX 100010
#define LL long long
using namespace std;

pair<LL,LL> bezout(LL a, LL b){
	pair<LL,LL> ans;
	bool swapped = 0;
	LL q, r;

	if(a < b){
		swap(a, b);
		swapped = 1;
	}
	

	if(b == 0){
		ans = {1, 0};
	}
	else{
		q = a / b;
		r = a % b;
		pair<LL,LL> MN = bezout(b, r);
		ans = {MN.second, MN.first - q * MN.second};
	}

	if(swapped)
		swap(ans.first, ans.second);
	return ans;
}

int main(){
	ifstream fin;
	ofstream fout;
	fin.open("inversmodular.in");
	fout.open("inversmodular.out"); 

	LL a, n;
	LL ans;
	fin >> a >> n;
	ans = bezout(a, n).first;
	if(ans < 0)
		ans = ans + n;
	fout << ans % n;
}