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

int64_t euclid(int64_t a, int64_t b, int64_t* coef_a, int64_t* coef_b)//euclid pentru a si b
{
    if(b==0)
    {
        *coef_a=1;//coeficientul lui a
        *coef_b=0;//coeficientul lui b
        return a;
    }

    int64_t coef_a_temp,coef_b_temp;
    int64_t cmmdc=euclid(b,a%b,&coef_a_temp,&coef_b_temp);

    *coef_a=coef_b_temp;
    *coef_b=coef_a_temp-(a/b)*coef_b_temp;

    return cmmdc;
}


int main(void)
{   
    int64_t N,A;
    
    FILE *fin=fopen("inversmodular.in","r");
    FILE *fout=fopen("inversmodular.out","w");
    
    if(fin==NULL)//verificam deschiderea fisierelor
    {
        perror("Eroare la deschiderea fisierului de citire.\n");
        exit(1);
    }
    if(fout==NULL)
    {
        perror("Eroare la deschiderea fisierului de scriere.\n");
        exit(1);
    }

    if((fscanf(fin,"%ld %ld",&A,&N))!=2)
    {
        perror("Eroare la citirea din fisier.\n");
        exit(1);
    }
    
    if(N<=A)//verificare conditie din enunt
    {
        perror("Numerele nu indeplinesc conditia.\n");
    }
    
    int64_t x,y;
    int64_t cmmdc=euclid(A,N,&x,&y);
    
    if(cmmdc!=1)
    {
        perror("Nu sunt prime intre ele cele 2 numere.\n");
    }
    else
    {   int64_t rezultat=0;
        if(x>0)
        {
            rezultat=x;
        }
        else
        {
            rezultat=x+N;
        }
        fprintf(fout,"%ld",rezultat);
    }
    
    if(fclose(fin)!=0)//verificam inchiderea fisierelor
    {
        perror("Eroare la inchiderea fisierului de citire.\n");
        exit(1);
    }
    
    if(fclose(fout)!=0)
    {
        perror("Eroare la inchiderea fisierului de scriere.\n");
        exit(1);
    }
    
    return 0;
}