#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;
}