//Include
#include <stdio.h>
using namespace std;

FILE *in, *out;
//Defintii
#define ll long long

//Functii
void euclid(int a,int b, ll *x, ll *y);

//Variabile
int num, mod;

//Main
int main()
{
	in = fopen("inversmodular.in", "rt");
	out = fopen("inversmodular.out", "wt");

    fscanf(in," %d%d ", &num, &mod);
    ll x, y;
    euclid(num, mod, &x, &y);

    if(x < 0)
        x = mod + x%mod;
    fprintf(out,"%lld\n", x);

	fclose(in);
	fclose(out);
	return 0;
}

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