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

void euclid(int a,int b, int *d,int *x,int *y)
{
    if(!b){*d=a; *x=1; *y=0;}
    else { int x0,y0;
    euclid(b,a%b,d,&x0,&y0);
    *x=y0;
    *y=x0-(a/b)*y0;  }


}

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

    int a,b;
    int *d,*x,*y;
    d=malloc(sizeof(int));
    x=malloc(sizeof(int));
    y=malloc(sizeof(int));
    scanf("%d %d",&a,&b);
    euclid(a,b,d,x,y);

    *x=(*x)%b;
    if((*x) < 0) *x = *x+b;
    printf("%d",*x);



    return 0;
}