#include <cstdio>

using namespace std;
int a,n,x,y;
void euclid(int a,int n)
{
    if(n==0)
    {
        x=1;
        y=0;
        return;
    }
    euclid(n,a%n);
    int x1=y;
    int y1=x-y*(a/n);
    x=x1;
    y=y1;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d %d",&a,&n);
    euclid(a,n);
    if(x<=0)
        x=n+x%n;
    printf("%d\n",x);
    return 0;
}