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

void cmmdc(int x, int y, int &a, int &b, int &gcd)
{
    int aa,bb;
    if(!y)
    {
        gcd=x;
        a=1;
        b=0;
        return;
    }

    cmmdc(y, x%y, aa, bb, gcd);
    a=bb;
    long long fg=((long long)gcd-(long long)a*x);
    b=fg/y;
}

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";
}