#include<stdio.h>
int A,N;

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

int inversmod(int a, int b) {
    int x,y;
    gcd(a,b,x,y);
    if(x<0) {
        int k = (-x-1)/N + 1;
        x += k*b;
    }
    return x%b;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&A,&N);
    printf("%d\n",inversmod(A,N));
    return 0;
}