#include <stdio.h>

long long extendedEuclid(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }

    long long x1, y1;

    long long gcd = extendedEuclid(b, a % b, &x1, &y1);

    *x = y1;
    *y = x1 - (a / b) * y1;

    return gcd;
}

int main(void)
{
    FILE *fr = fopen("inversmodular.in", "r");
    FILE *fw = fopen("inversmodular.out", "w");

    if(!fr)
    {
      fprintf(stderr,"Failed to open read file");
      return -1;
    }

    if(!fw)
    {
      fprintf(stderr,"Failed to open write file");
      fclose(fr);
      return -1;
    }

    long long A, N;
    long long x, y;

    fscanf(fr, "%lld %lld", &A, &N);

    extendedEuclid(A, N, &x, &y);

    x = (x % N + N) % N;

    fprintf(fw, "%lld", x);

    fclose(fr);
    fclose(fw);

    return 0;
}