#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

#define DMAX 2000003
#define ll long long 

ll A, N, X, Y, D;

ll egcd(ll a, ll b, ll &x, ll &y){
	ll d, aux;
	if (b == 0){
		x == 1;
		y == 0;
		return a;
	}
	else{
		d = egcd(b, a%b, x, y);
		aux = x;
		x = y;
		y = aux - (a / b)*y;
		return d;
	}
}

int main(){
	ll i, j;

	//freopen("test.in", "r", stdin);
	freopen("inversmodular.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	freopen("inversmodular.out", "w", stdout);

	cin >> A >> N;
	egcd(A, N, X, Y);
	cout << X;

	return 0;
}