#include <iostream>
#include <fstream>

using namespace std;

void gcd( int a, int b, int &x, int &y )
{
    if ( !b )
    {
        x = 1;
        y = 0;
    }
    else
    {
        int x0, y0;
        gcd( b, a % b, x0, y0 );
        x = y0;
        y = x0 - ( a / b ) * y0;
    }
}

int A, N;

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

    f >> A >> N;

    int x, y;

    gcd( A, N, x, y );

    if ( x <= 0 ) x = N + x % N;

    g << x << "\n";

    return 0;
}