#include <iostream>
#include <fstream>
using namespace std;
int a,n;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
void calc(long long &x,long long &y,int a1,int a2)
{
    if(!a2){x=1; y=0;}
    else
    {
        calc(x,y,a2,a1%a2);
        long long aux=x;
        x=y; y=aux-y*(a1/a2);
    }
}
void solve()
{
    long long ins=0,inv; f>>a>>n;
    calc(inv,ins,a,n);
    if(inv<=0)inv=n+inv%n;
    g<<inv;
}
int main()
{
    solve();
    return 0;
}