#include <stdio.h>

/*
Se dau doua numere A si N, cu 1 ≤ A ≤ N-1, prime intre ele (cel mai mare divizor comun al lor este 1). Sa se determine X intre 1 si N-1 astfel incat A * X sa fie congruent cu 1, modulo N (restul impartirii lui A * X la N sa fie 1). Numarul X se va numi inversul modular al lui A.
*/
int main()
{
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");

    long long A, N;
    fscanf(fin, "%lld", &A);
    fscanf(fin, "%lld", &N);

    for (long long i = 1; i < N; i++)
    {
        if ((A * i) % N == 1)
        {
            fprintf(fout, "%lld", i);
            break;
        }
    }

    return 0;
}