#include<stdio.h>

FILE *f=fopen("inversmodular.in","r"), *g=fopen("inversmodular.out","w");

int A, N, X, Y;

void cmmdc( int a, int n, int &x, int &y ){
int x0, y0;

    if( n == 0 ){
        x = 1;
        y = 0;
        return;
    }

    cmmdc( n, a%n, x0, y0 );

    x = y0;
    y = x0 - (a/n) * y0;
}

int main(){

    fscanf(f,"%d %d\n",&A,&N);

    cmmdc(A,N,X,Y);

    while( X < 0 )
        X += N;

    fprintf(g,"%d\n",X);

return 0;
}