#include <iostream>
#include <fstream>
using namespace std;
ifstream f1("inversmodular.in");
ofstream f2("inversmodular.out");
int A,N,X;

void euclidext(int a, int b, int &k, int &l)
{
    if(b==0)
    {
        k=1;
        l=0;
        return;
    }
    int kp,lp;
    euclidext(b,a%b,kp,lp);
    k=lp;
    l=kp-lp*(a/b);

}

int main()
{
    f1>>A>>N;
    int k,l;
    euclidext(A,N,k,l);
    while(k<1) k+=N;
    f2<<k;
    return 0;
}