/*#include <cstdio>

using namespace std;
int euclid(int a,int b,int &x,int &y);
int main()
{
    int a,b,c,t;
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        int rez1,rez2,sol;
        scanf("%d%d%d",&a,&b,&c);
        rez1=rez2=1<<17;
        sol=euclid(a,b,rez1,rez2);
        if(c%sol){
            printf("0 0 \n");
        }
        else printf("%d %d\n",rez1*(c/sol),rez2*(c/sol));
    }
    return 0;
}
int euclid(int a,int b,int &x,int &y)
{
    if (b==0){
       x=1;y=0;
       return a;
    }
    else{
        int x1,y1;
        int d;
        d=euclid(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
        return d;
    }
}
*/
#include <cstdio>

using namespace std;
long long euclid(long long a,long long b,long long &x,long long &y);
int main()
{
    long long a,b;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long rez1,rez2,sol;
    scanf("%lld%lld",&a,&b);
    rez1=rez2=1<<17;
    sol=euclid(a,b,rez1,rez2);
    while(rez1<0)rez1+=b;
    printf("%lld\n",rez1);
    return 0;
}
long long euclid(long long a,long long b,long long &x,long long &y)
{
    if (b==0){
       x=1;y=0;
       return a;
    }
    else{
        long long x1,y1;
        long long d;
        d=euclid(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
        return d;
    }
}