#include<cstdio>

using namespace std;

int a,n;
int keepx,keepy,oldx,oldy;

void solve(int v1,int v2)
{
    if(v2==0)
    {
        oldx=v1;
        oldy=0;
        return;
    }
    solve(v2,v1%v2);
    keepx=oldy;
    keepy=oldx-(v1/v2)*oldy;
    keepx%=n;
    keepy%=n;
    oldx=keepx;
    oldy=keepy;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    scanf("%d %d",&a,&n);

    solve(a,n);

    printf("%d",keepx);
}