#include <fstream>
#include <vector>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
vector <long long> prim;
long long baza,n,a,b;
void euclid(long long a, long long b, long long &x, long long &y)
{
    if (b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        long long x0,y0;
        euclid(b,a%b,x0,y0); ///& (ampersantul) imi calculeaza val lui x0,y0
        x=y0; ///formula de recurenta
        y=x0-a/b*y0;
    }
}
int main()
{cin>>baza>>n;
euclid(baza,n,a,b);
a=(a%n+n)%n;
cout<<a;
    return 0;
}