#include <stdio.h>
#include <vector>
#define ll long long
using namespace std;

int n,a;
ll x,y;

void invers_modular(int a,int b,ll &x,ll &y)
{
    if (!b) x = 1,y = 0;
    else
    {
        ll x0,y0;
        invers_modular(b,a%b,x0,y0);
        x = y0;
        y = x0 - (a/b) * y0;
    }
}

int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    scanf("%i%i",&a,&n);
    invers_modular(a,n,x,y);
    if (x <= 0) x = n + x%n;
    printf("%lld",x);
    fclose(stdin);
    fclose(stdout);
    return 0;
}