#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void EuclidExtins(int A, int B, int D, int &X, int &Y)
{
	if (B == 0)
	{
		X = 1;
		Y = 0;
		D = A;
	}
    else {
        int X0, Y0;
        EuclidExtins(B, A % B, D, X0, Y0);
        X = Y0;
        Y = X0 - (A / B) * Y0;
    }
}

int main()
{
    int a, n, d, x, y;
    f >> a >> n;
    EuclidExtins(a, n, d, x, y);
    while (x < 0)
        x = x + n;
    g << x;
    return 0;
}