// A*X+N*Y=cmmdc(A,N)
#include <stdio.h>
#include <stdlib.h>

void citire(long long int *A, long long int *N)
{
    FILE *f;
    if ((f=fopen("inversmodular.in", "r"))==NULL)
    {
        fprintf(stderr,"eroare deschidere fisier\n");
        exit(1);
    }
    if(fscanf(f, "%lld %lld", A, N)!=2)
        exit(1);
    fclose(f);
}

void afisare(long long int X)
{
    FILE *g;
    if((g=fopen("inversmodular.out", "w"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }
    fprintf(g, "%lld", X);
    fclose(g);
}

long long int inv_modular(long long int A, long long int N)
{
    long long int b=N;
    long long int cat, rest, aux;
    long long int X=1,Y=0; // din formula
    if (b==1)
        return 0;
    while (b!=0)  // euclid extins
    {
        rest=A%b;

        cat=A/b;
        aux=X-cat*Y;
        X=Y;
        Y=aux;

        A=b;
        b=rest;
    }
    while (X<0)  // daca este negativ rezultatul il aducem in intervalul [1, N-1]
    {
        X+=N;
    }
    return X;
}

int main()
{
    long long int A, N, X;
    citire(&A, &N);
    X=inv_modular(A, N);
    afisare(X);
    return 0;
}