#include <stdio.h>

#define ll long long

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

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    
    ll a,n,sol,x;
    
    scanf("%lld%lld", &a,&n);
    
    ee(a,n,sol,x);
    
    while (sol < 0) 
          sol += n;
    printf("%lld\n", sol);
        
    return 0;    
}