#include<stdio.h>

inline void gcd(long long &inv,long long &ins,int a,int n)
{
    if(!n)
    {
        inv=1;
        ins=0;
    }
    else
    {
        gcd(inv,ins,n,a%n);

        long long aux=inv;
        inv=ins;
        ins=aux-ins*(a/n);
    }
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int a,n;
    long long inv=0,ins=0;
    scanf("%d%d",&a,&n);

    gcd(inv,ins,a,n);

    if(inv<=0)
        inv+n+inv%n;

    printf("%lld\n",inv);

    return 0;
}