#include<stdio.h>
long long hcf(long long a,long long b){
    long  long r = a % b;
    while(r){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
//recursive version
/*long long fme(long long g,long long x,long long p){
    long long a;
    if(x == 1)
        return g;
    if(x % 2 == 0)
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p ) % p;
    else
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p * g ) % p;
    return a;
}*/
//iterative version
long long fme(long long g, long long x, long long p){
    long long a = 1;
    while(x){
        if(x % 2 == 1)
            a = (a * g) % p;
        g = (g * g) % p;
        x /= 2;
    }
    return a;
}
long long dl(long long y, long long g, long long p){
    long long a = 1;
    int i = 0;
    for(i = 1; i <= p; i ++){
        a = (a * g) % p;
        if(a == y)
            break;
    }
    return i;
}
void gcd(long long a, long long b, long long *x, long long *y){
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }
    long long xa,ya;
    gcd(b,a%b,&xa,&ya);
    *x = ya;
    *y = xa - (a / b) * ya;
}
long long imp(long long a, long long b){
    long long x,y;
    x = y = 0;
    gcd(a,b,&x,&y);
    if(y<0)
        y = ( y + ( (-y) / a + 1 ) * a ) % a;
    return y;
}
int main(int argc, char **argv){
    long long a,b,c;
    long long t;
    FILE *f,*g;
    //Part 1 testing
    /*f = fopen("euclid2.in","r");
    g = fopen("euclid2.out","w");
    fscanf(f,"%lld",&t);
    while(t--){
        fscanf(f,"%lld%lld",&a,&b);
        c = hcf(a,b);
        fprintf(g,"%lld\n",c);
    }
    fclose(f);
    fclose(g);*/

    //Note, for this part, I will implement both an iterative and a
    //recursive version of the algorithm
    //Part 2 testing
    /*f = fopen("lgput.in","r");
    g = fopen("lgput.out","w");
    long long MOD = 1999999973;
    fscanf(f,"%lld%lld",&a,&b);
    c = fme(a,b,MOD);
    fprintf(g,"%lld",c);
    fclose(f);
    fclose(g);*/

    //Part 3 testing
    /*int t;
    long long a,b,c;
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&a,&b,&c);
        printf("%lld\n",dl(b,a,c));
    }*/

    /*f = fopen("euclid3.in","r");
    g = fopen("euclid3.out","w");
    fscanf(f,"%lld",&t);
    while(t--){
        fscanf(f,"%lld%lld%lld",&a,&b,&c);
        long long d,x,y;
        d = x = y = 0;
        d = gcd(a,b,&x,&y);
        if(c % d == 0)
            fprintf(g,"%lld %lld\n",x*c/d,y*c/d);
        else
            fprintf(g,"0 0\n");
    }
    fclose(f);
    fclose(g);*/

    //Part 4
    f = fopen("inversmodular.in","r");
    g = fopen("inversmodular.out","w");
    fscanf(f,"%lld%lld",&a,&b);
    fprintf(g,"%lld",imp(b,a));
    fclose(f);
    fclose(g);
    return 0;
}