#include <stdio.h>
#define ll long long
int a,n;
void euclid(ll &x, ll &y, int a, int b)
{
    ll aux;
     if (!b)
         x = 1, y = 0;
     else
     {
         euclid(x,y,b,a%b);
         aux = x;
         x=y;
         y=aux-y*(a/b);
     }
}
int main()
{
    ll inv=0, ins;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d %d",&a,&n);
    euclid(inv,ins,a,n);
    if (inv<=0)
       inv=n+inv%n;
    printf("%lld\n", inv);
    return 0;
}