#include <iostream>
#include <cstdio>

using namespace std;
long long invers(int a, int m)
{
    long long y0=0, y1=1,y;
    long long aux=m;
    long long r,c;
    while(a!=0)
    {
        r=m%a;
        c=m/a;
        m=a;
        a=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
    if(y0<0)
        return m+y0%m;
    return y0;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int a,m;
    scanf("%d %d", &a, &m);
    cout<<invers(a,m);
    return 0;
}