#include <cstdio>

using namespace std;

void extended_gcd(int a,int b,int *d,int *x,int *y)
{
    if(b!=0) {
        int x0,y0;
        extended_gcd(b,a%b,d,&x0,&y0);
        *x=y0;
        *y=x0-a/b*y0;
    }
    else {
        *d=a;
        *x=1;
        *y=0;
    }
}


int main()
{

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

    int a,n,x,y,d;

    scanf("%d %d",&a,&n);
    extended_gcd(a,n,&d,&x,&y);
    while(x<0) {
        x+=n;
    }
    printf("%d\n",x);
    return 0;
}