#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n,i,j;
void Euclidext(int a,int b,int &d,int &x,int &y)
      {if(b==0)
         {d=a;
          x=1;
          y=0;
         }
        else
        {int x0,y0;
         Euclidext(b,a%b,d,x0,y0);
         x=y0;
         y=x0-y0*(a/b);
        }
      }
int main()
{int x,y,d;
 fin>>a>>n;
 Euclidext(a,n,d,x,y);
 while(x<0)x=x+n;
 fout<<x;
}