#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");

struct formula
{
    int rez, cat, a, r;
};
struct ec
{
    int rez, st, a, dr, b;
} aux;
vector<formula>ecuatie;
vector<ec>invers;
vector<ec>sol;
int cmmdc(int a, int b)
{
    int r, cat;
    int minim = min(a, b);
    int maxim = max(a, b);
    a = maxim;
    b = minim;
    while(b)
    {
        cat = a / b;
        r = a % b;

        if(r != 0)
            ecuatie.push_back({a, cat, b, r});

        a = b;
        b = r;
    }
    return a;
}
void afisare(int val, int x, int y)
{
    for(int i=ecuatie.size() - 1; i>=0; i--)
    {
        ///fout<<ecuatie[i].rez<<" = "<<ecuatie[i].cat<<" * "<<ecuatie[i].a<<" + "<<ecuatie[i].r<<"\n";

        aux.rez = ecuatie[i].r;
        aux.st = 1;
        aux.a = ecuatie[i].rez;
        aux.dr = -ecuatie[i].cat;
        aux.b = ecuatie[i].a;

        invers.push_back(aux);

    }
    invers.push_back(aux);
    int coef_st, termen_st, coef_dr, termen_dr;
    for(int i=0; i<invers.size()- 1; i++)
    {
        ///cout<<invers[i].rez<<" = "<<invers[i].st<<" * "<<invers[i].a<<"  "<<invers[i].dr<<" * "<<invers[i].b<<"\n";
        ///i % 2 == 0 modific pe cel din dreapta, contrar pe cel din stanga
        if (i % 2 == 0)
        {
            coef_st = invers[i].dr * invers[i + 1].dr + invers[i].st;
            termen_st = invers[i].a;
            coef_dr = invers[i].dr * invers[i + 1].st;
            termen_dr = invers[i + 1].a;
        }
        else
        {
            coef_st = invers[i].st * invers[i + 1].st;
            termen_st = invers[i + 1].a;
            coef_dr = invers[i].st * invers[i+1].dr + invers[i].dr;
            termen_dr = invers[i].b;
        }
        sol.push_back({val, coef_st, termen_st, coef_dr, termen_dr});
        swap(invers[i + 1], sol[ sol.size() - 1 ]);
    }
    int answer;
    int k =invers.size() - 2;

    if(invers[ k ].a == x)
        answer = invers[k].st;
    if(invers[ k ].b == x)
        answer = invers[k].dr;

    while(answer < 0)
    {
        answer = (answer + y) % y;
    }
    fout<<answer<<"\n";
}
void citire()
{
    int x, y, val;
    fin>>x>>y;
    val = cmmdc(x, y);
    afisare(val, x, y);
}
int main()
{
    citire();
    return 0;
}