#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("euclid3.in", ios::in);
fstream f2("euclid3.out", ios::out);
int32_t a, b;
int32_t q, r0, r1, r, s0, s1, s, t0, t1, t;
///d=cmmdc(a, b)
int main()
{
    ///a*x+b*y=cmmdc(a, b) echiv
    ///a*x+n*y=1 echiv
    ///(a*x)%n=1
    f1>>a>>b;
    r0=a; r1=b;
    s0=1; s1=0;
    t0=0; t1=1;
    do
    {
        q=r0/r1;
        r=r0-r1*q;
        s=s0-s1*q;
        t=t0-t1*q;

        r0=r1; s0=s1; t0=t1;
        r1=r; s1=s; t1=t;
    }
    while(r!=0);

    ///d=r0=1
    ///sol= s0, t0 (normal sunt s1, si t1 dar deja ai facut atribuirile pt urmatorul pas)
    ///deoarece s0<0 adaugam repetat a s0 b(=n in problema)
    while(s0<0) s0+=b;
    f2<<s0;

    return 0;
}