#include <stdio.h>

int A, N;

void cmmdc(int a,int b,int *d,int *k,int *l)
{
    if(b==0)
    {
        *d=a;
        *k = 1;
        *l = 0;
    }
    else
    {
        int k0, l0;
        cmmdc(b,a%b,d,&k0,&l0);

        *k = l0;
        *l = k0 - (a/b)*l0;
    }
}

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

    int x,y,d;

    cmmdc(A,N,&d,&x,&y);

    printf("%d",x);

    return 0;
}