#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int n;
int a,b,c;

int euclid(int a,int b,int &x,int &y)
{
    if(b==0)
    {


        x=1;
        y=0;
        return a;
    }
    int x0;
    int y0;
    int rez;
    rez = euclid(b,a%b,x0,y0);

    x= y0;
    y= x0 - (a/b) * y0;

    return rez;

}

int main()
{


    int mod;
    int nr;
    fin>>nr>>mod;
    int d,x,y;
    d=euclid(nr,mod,x,y);

    while(x<=0)
        x=(x+mod)%mod;

    fout<<x<<'\n';




}