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

void inversmodular(FILE *fis,FILE *gis)
{
    long long int a=0,n=0,y=0,y0=0,y1=1,aux=0,r=0,c=0;
    fscanf(fis,"%lld",&a);
    fscanf(fis,"%lld",&n);
    aux=n;
    while(a!=0)
    {
        r=n%a;
        c=n/a;
        n=a;
        a=r;
        y=y0-c*y1;
        y0=y1;
        y1=y;
    }
    while(y0<0)
    {
        y0=aux+y0;
    }
    fprintf(gis,"%lld\n",y0);
}
int main(void)
{   
    FILE *fis=NULL,*gis=NULL;
    fis=fopen("inversmodular.in","r");
    if(fis==NULL)
    {
        perror("eroare la deschidere fisier de intrare\n");
        exit(-1);
    }
    gis=fopen("inversmodular.out","w");
    if(gis==NULL)
    {
        perror("eroare la deschidere fisier de iesire\n");
        exit(-1);
    }
    inversmodular(fis,gis);
    fclose(fis);
    fclose(gis);

    return 0;
}