#include <iostream>
#include <fstream>

using namespace std;

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

typedef pair<int,int> gcdres;
gcdres gcd(int x, int y){
	if(y == 0){
		return {1, 0};
	}else{
		gcdres res = gcd(y, x%y);
		return {res.second, res.first - res.second*(x/y)};
	}
}

int invmod(int a, int n){
	return gcd(a, n).first;
}

int a, n;

int main(){
	fin >> a >> n;
	fout << invmod(a, n);
	return 0;
}