// trebuie sa aflu X a.i:
// (A*X)%N=1 => A*X=k*N+1 => A*X-k*N=1
// notez -k=Y => A*X+N*Y=1
// principiul extins Euclid: A*X+N*Y=cmmdc(A,N)
// A, N prime intre ele => cmmdc(A,N)=1
// => algoritmul lui Euclid extins va gasi X cerut


#include <stdio.h>

long long euclid_extins(long long A, long long N)
{
    long long x0 = 0, x1 = 1;
    long long aux = N;
    long long c, r, x;
    while (A != 0)
    {
        r = N % A;
        c = N / A;

        N = A;
        A = r;

        x = x0 - c * x1;
        x0 = x1;
        x1 = x;
    }
    while (x0 < 0)
    {
        x0 += aux;
    }
    return x0;
}

int main(void)
{
    FILE *fin = fopen("inversmodular.in", "r");
    if (fin == NULL)
    {
        return 1;
    }
    FILE *fout = fopen("inversmodular.out", "w");
    if (fout == NULL)
    {
        fclose(fin);
        return 1;
    }
    long long A, N;
    fscanf(fin, "%lld %lld", &A, &N); // citire A,N

    long long invers_modular = euclid_extins(A, N);

    fprintf(fout, "%lld\n", invers_modular); // scriere rezultat in fisier

    fclose(fin);
    fclose(fout);
    return 0;
}