#include<stdio.h>

void euclidext(int a,int b,int& x,int& y){

    if(b==0){

        x=1;
        y=0;
        return ;
    }

    int q=a/b;
    int nx,ny;
    euclidext(b,a-q*b,nx,ny);
    x=ny;
    y=nx-q*ny;

}




int main(){


    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    int a,n,x,y;
    scanf("%d%d",&a,&n);
    euclidext(a,n,x,y);
     while(x<0){
        x+=n;
    }
    while(x>n){
        x-=n;
    }

    printf("%d",x);

    return 0;
}