#include <cstdio>

using namespace std;

int a,n,x=0,y=0,d=0;

void euclid (int a,int b,int&x,int&y)
    {
        if (b==0)
           {
               x=1;
               y=0;
           }
        else
           {
               int x0=0,y0=0;
               euclid(b,a%b,x0,y0);
               y=x0-(a/b)*y0;
               x=y0;
           }
    }
int main()
    {
        freopen("inversmodular.in","r",stdin);
        freopen("inversmodular.out","w",stdout);
        scanf("%d%d",&a,&n);
        euclid(a,n,x,y);
        while (x<0) x+=n;
        printf("%d\n",x);
    }