#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
typedef long long Int;
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%=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 X,Y;
    cmmdc(b,a%b,X,Y);
    x=Y;
    y=X-a/b*Y;
}