#include <iostream>
#include <fstream>
#define InFile  "inversmodular.in"
#define OutFile "inversmodular.out"

using namespace std;

ifstream fin  (InFile);
ofstream fout (OutFile);

void euclid (int a, int b, long long int &x, long long int &y);
long long int mod_inv (int a, int n);

unsigned int A, N;

unsigned int X;

int main()
{
    fin >> A >> N;
    X = mod_inv(A,N);
    fout << X;
    return 0;
}

void euclid (int a, int b, long long int &x, long long int &y)
{
    long long int xx, yy;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    euclid(b,a%b,xx,yy);
    x = yy;
    y = xx - yy*(a/b);
}

long long int mod_inv (int a, int n)
{
    long long inv, ins;
    euclid(a,n,inv,ins);
    if (inv <= 0)
        inv = n + inv%n;
    return inv;
}