#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 main()
{
    FILE *f,*g;
    f=fopen(fin,"r");
    g=fopen(fout,"w");
    int a,M;
    fscanf(f,"%d%d",&a,&M);
    fprintf(g,"%d\n",solve(a,M));
    fclose(f);
    fclose(g);
    return 0;
}