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