#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

const int NMAX = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int a, n, x, y, d;

void read()
{
    in>>a>>n;
}

void euclid(int a, int b, int &d, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        d = a;
        return;
    }
    int x1, y1;
    euclid(b, a % b, d, x1, y1);
    x = y1;
    y = x1 - a / b * y1;
}

void solve()
{
    euclid(a, n, d, x, y);
    while (x<0) x+=n;
    out<<x;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    read();
    solve();

    return 0;
}