#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");

ofstream fout("inversmodular.out");

void gcd(long long N, long long  M, long long &x, long long  &y)
{
    if (M == 0)
    {
        x = 1, y = 0;
        return;
    }
    else
    {
        gcd(M, N % M, x, y);
        long long aux=x;
        x = y;
        y = aux - (N / M) *y;
    }
}

int main()
{
    long long a, n, x = 0, y = 0;
    fin >> a >> n;
    gcd(a, n, x, y);
    if (x <= 0)
        x = n + x % n;
    fout << x;
}