#include <bits/stdc++.h>

using namespace std;

void cmmdc(int &x, int &y, int a, int b)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        cmmdc(x, y, b, a % b);
        int aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int A, N;
    fin >> A >> N;
    int x, y;
    cmmdc(x, y, A, N);
    if (x < 0)
        x = N + x % N;

    fout << x << endl;
}