#include <stdio.h>

void InvMod (int a, int b, int *alpha, int *beta)
{
    if (b == 0)
    {
        *alpha = 1;
        *beta = 0;
    }
    else
    {
        InvMod (b, a % b, alpha, beta);
        
        int aux = *alpha;
        *alpha = *beta;
        *beta = aux - (*beta) * (a / b);
    }   
}

int main ()
{
    int y, iA, A, N;

    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);

    scanf ("%d %d", &A, &N);
    InvMod (A,N,&iA,&y);

    while (iA <= 0)
        iA += N;
    printf("%d\n", iA);

    return 0;
}