#include <stdio.h>
#include <stdlib.h>

#define fin "inversmodular.in"
#define fout "inversmodular.out"

/*
void euclid_extins(int *x,int *y,int a,int b){
    if(!b){
        *x=1;
        *y=0;
    }
    else{
        euclid_extins(x,y,b,a%b);
        int aux=*x;
        *x=*y;
        *y=aux-(*y)*(a/b);
    }
}

int solve(int a,int M){
    int inv,ins;
    euclid_extins(&inv,&ins,a,M);
    if(inv<=0){
        inv=M+inv%M;
    }
    return inv;
}
*/

int euclid_gcd(int a,int b){
    if(b==0){
        return a;
    }
    return euclid_gcd(b,a%b);
}

void euclid_extins(int a,int b,int d,int *x,int *y){
    int r0=a,r1=b;
    int x0=1,x1=0;
    int y0=0,y1=1;
    while(r1!=0){
        int q=r0/r1,aux;
        aux=r1;
        r1=r0-q*r1;
        r0=aux;

        aux=x1;
        x1=x0-q*x1;
        x0=aux;

        aux=y1;
        y1=y0-q*y1;
        y0=aux;
    }
    *x=x0;
    *y=y0;
}

int main()
{
    FILE *f,*g;
    f=fopen(fin,"r");
    g=fopen(fout,"w");
    int a,M;
    fscanf(f,"%d%d",&a,&M);
    int x,y;
    euclid_extins(a,M,1,&x,&y);
    while(x<0){
        x+=M;
    }
    fprintf(g,"%d\n",x);
    fclose(f);
    fclose(g);
    return 0;
}