//Problema Invers modular - Rezolvare C++: 100p -> infoarena.ro
//Stud. Cristian CRIȘAN - AC, CTI-RO, ANUL I

#include <iostream>
#include <fstream>

using namespace std;

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

void read(int &a, int &M)
{
    fin >> a >> M;
}

void solve_iter(int a, int M) //varianta iterativa a rezolvarii
{
    int y0 = 0, y1 = 1, aux, r, c, y ;
    aux = M;
    while (a)
    {
        r = M % a;
        c = M / a;
        M = a;
        a = r;
        y = y0 - c * y1;
        y0 = y1;
        y1 = y;
    }
    while (y0 < 0)
        y0 += aux;
    fout << y0;
}

void solve_rec(int &x, int &y, int a, int b) //varianta recursiva a rezolvarii
{
    if(b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        int x1 , y1;
        solve_rec(x1, y1, b, a%b);
        x = y1;
        y = x1 - y1 * (a / b);
    }
}

int main()
{
    int a, M, inv = 0, ins = 0;
    read(a, M);
    solve_iter(a, M);
    /*solve_rec(inv, ins, a, M);
    if(inv <= 0)
        inv = M + inv % M;
    fout << inv;**/
    return 0;
}