#include<stdio.h>

int gcd(int A,int B,int &X,int &Y)
{
    if (B==0)
        {
        X=1;
        Y=0;
        return A;
        }

    int D,X0,Y0;
    D = gcd(B,A%B,X0,Y0);

    X = Y0;
    Y = X0 - (A/B)*Y0;
    return D;
}

int main()
{
    int A,N,D,X,Y;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&A,&N);

    D=gcd(A,N,X,Y);
    for(;X<0;X+=N);

    printf("%d\n",X);
    return 0;
}