#include <fstream>


using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");


struct vec
{
    int a1, a2;
};

int a, n, sol;

int main()
{
    int aux;
    vec v1, v2, v3;
    fin>>a>>n;
    v1.a1=v2.a2=1;
    v1.a2=v2.a1=0;

    while(n%a)
    {
        v3.a1=v1.a1-(n/a)*v2.a1;
        v3.a2=v1.a2-(n/a)*v2.a2;
        aux=n%a;
        n=a;
        a=aux;
        v1=v2;
        v2=v3;
    }
    sol=(n*v2.a1+a*v2.a2)%n;
    if( sol>0 )
    fout<<sol;
    else fout<<n-sol;
    return 0;
}