#include <bits/stdc++.h>

using namespace std;

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

struct Str{
    int d,x,y;
};
Str EuclidExtins(int d, int a,int b){
    if(b == 0){
        return {a, 1, 0};
    }
    Str d_p = EuclidExtins(d, b, a - (a / b) * b);
    return {d, d_p.y, d_p.x - a / b * d_p.y};
}
int main()
{
    int a,n;
    f >> a >> n;
    Str t = EuclidExtins(1,a,n);
    if(t.x < 0){
        t.x += n;
    }
    g << t.x;
    return 0;
}