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