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

int64_t Euclid_EXT(int64_t a,int64_t b,int64_t* x,int64_t* y)
{
    if(b==0)
    {
        *x=1;
        *y=0;
        return a;
    }
    int64_t x1,y1;
    int64_t d=Euclid_EXT(b,a%b,&x1,&y1);
    *x=y1;
    *y=x1-(a/b)*y1;
    return d;
}

int main(void)
{   
    FILE *fin=fopen("inversmodular.in","r");
    FILE *fout=fopen("inversmodular.out","w");
    if(fin==NULL || fout==NULL)
    {
        fprintf(stderr,"eroare la deschiderea fisierelor");
        exit(EXIT_FAILURE);
    }
    int64_t N,A;
    if((fscanf(fin,"%ld %ld",&A,&N))!=2)
    {
        fprintf(stderr,"eroare la citirea din fisier");
        exit(EXIT_FAILURE);
    }
    int64_t x,y;
    int64_t cmmdc=Euclid_EXT(A,N,&x,&y);
    if(cmmdc!=1)
    {
        fprintf(fout,"Nu eista!!!!\n");
    }
    else
    {   int64_t res=0;
        if(x>0)
        {
            res=x;
        }
        else
        {
            res=x+N;
        }
        fprintf(fout,"%ld\n",res);
    }
    if((fclose(fin))!=0)
    {
        fprintf(stderr,"eroare la inchiderea fisierului de citire");
        exit(EXIT_FAILURE);
    }
    if((fclose(fout))!=0)
    {
        fprintf(stderr,"eroare la inchiderea fisierului de scriere");
        exit(EXIT_FAILURE);
    }
    return 0;
}