#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
    {long long x0,y0;
        gcd(M, N % M, x0, y0);
        x = y0;
        y = x0 - (N / M) *y0;
    }
}

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