#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long x[101],y[101],a,n,d,D;

long long euclid(long long A, long long B, long long i)
{
    if(B==0)
    {
        x[i]=1;
        y[i]=0;
        return A;
    }
    d=euclid(B,A%B,i+1);
    x[i]=y[i+1];
    y[i]=x[i+1]-(A/B)*y[i+1];
    return d;
}

int main()
{
    f>>a>>n;
    D=euclid(a,n,1);
    if(D<=0) D=n+D%n;
    g<<D;
    return 0;
}