//
//  main.c
//  invers_modular
//
//  Created by Bran Eduard Denis on 31.05.2023.
//

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

void euclid(int a, int n, int* x, int* y)
{
    if(n==0)
    {
        *x=1;
        *y=1;
    }
    else
    {
        int x1 , y1;
        euclid(n,a%n,&x1,&y1);
        *x=y1;
        *y=x1-a/n*y1;
    }
}

int main()
{
    int A,N,x,y;
    FILE * f;
    f=fopen("inversmodular.in","rt");
    
    if(f==NULL)
    {
        printf("Eroare");
        return 0;
    }
    
    fscanf(f,"%d %d",&A,&N);
    
    euclid(A,N,&x,&y);
    
    while(x<0)
        x=x+N;
    
    f=fopen("inversmodular.out","wt");
    if(f==NULL)
    {
        printf("Eroare");
        return 0;
    }
    
    fprintf(f,"%d",x);
    fclose(f);
    return 0;
}