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

using namespace std;

//Determina inversul modular

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

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

int main(){
	ll a,n,x,y;
	fin>>a>>n;
	euclid(n,a,x,y);
	fout<<x;
	return 0;
}