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

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

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