//Ilie Dumitru
#include<cstdio>

int div;

void cmmdc_ext(int x, int y, int &a1, int &a2)
{
    if(y)
    {
        cmmdc_ext(y, x%y, a1, a2);
        int aux=a2;
        a2=a1-(x/y)*a2;
        a1=aux;
    }
    else
    {
        div=x;
        a1=1;
        a2=0;
    }
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int N, A, x, y;
    scanf("%i%i", &A, &N);
    fclose(stdin);
    cmmdc_ext(A, N, x, y);
    while(x<0)
        x+=N;
    printf("%i", x);
    fclose(stdout);
    return 0;
}