#include <stdio.h>

int A, N;

void cmmdc(int a,int b,int *d,long long int *k,long long int *l)
{
    if(b==0)
    {
        *d=a;
        *k = 1;
        *l = 0;
    }
    else
    {
        long long 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);

    long long int x,y;
    int d;

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

    while(x<0) x+=N;

    printf("%lld",x);

    return 0;
}