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

void cmmdc(int a, int b, int &x, int &y, int &rez)
{
    if(!b)
    {
        rez=a;
        x=1;
        y=0;
    }
    else
    {
        int yy,xx;
        cmmdc(b, a%b, xx, yy, rez);
        x=yy;
        y=(rez-a*x)/b;
    }
}

int main()
{
    int a, n, rez, x=0, y=0;
    fin>>a>>n;
    cmmdc(a, n, x, y, rez);

    while(x<0)
        x+=n;
    while(x>n)
        x-=n;
    fout<<x<<"\n";
}