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

using num = long long;

// ax + by = g
// ax - (a/b)bx + by + (a/b)bx = g
// (a - (a/b)b)x + b(y + (a/b)x) = g

constexpr num normalizeaza_modulo(const num a, const num b){
	return (a < 0) ? normalizeaza_modulo(a+b, b) : a%b; }

tuple<num, num> euclid_extins(num a, num b){
	if(b == 0){
		return make_tuple(1, 0); }
	else{
		num x1, y1;
		tie(y1, x1) = euclid_extins(b, a%b);
		return make_tuple(x1, y1 - (a/b) * x1); } }

int main(){
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	num a, b;
	f >> a >> b;
	const num rez1 = get<0>(euclid_extins(a, b)),
		rez = normalizeaza_modulo(rez1%b, b);
	g << rez;
	return 0; }