#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int x, y;

void euclid(int a, int b) {
	if (b==0) {
		x=1;
		y=0;
		return;
	}
	euclid(b, a%b);
	int tx=y;
	int ty=x-y*(a/b);
	x=tx;
	y=ty;
}

int main() {
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	int a, b;
	fin >> a >> b;
	euclid(a, b);
	x%=b;
	if (x<0) x+=b;
	fout << x;
	return 0;
}