#include <bits/stdc++.h>
#define INT long long int
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
INT n,a,x,y,d;
void cmmdc(INT,INT,INT&,INT&);
int main()
{
    fin>>a>>n;
    INT x,y;
    cmmdc(a,n,x,y);
    x=x%n;
    if(x<0)x+=n;
    fout<<x;
    return 0;
}
void cmmdc(INT a,INT b,INT &x,INT &y)
{
    if(b==0){x=1;y=0;return;}
    INT x0,y0;
    cmmdc(b,a%b,x0,y0);
    x=y0;
    y=x0-a/b*y0;
}
//pair<int, int> p;
//
//pair <int, int> euclid(int x, int y){
//    if(y==0)
//        return {1, 0};
//    p=euclid(y,x%y);
//    return {p.second, p.first - (x/y)*p.second };
//}