//
//  main.cpp
//  inversmodular
//
//  Created by Robert Badea on 12/10/13.
//  Copyright (c) 2013 Robert Badea. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;


int main(int argc, const char * argv[])
{

    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    
    int a, b, x, y, s, t, u, v;
    
    in >> a >> b;
    
    x = a; y = b; s = 0; t = 1; u = 1; v = 0;
    
    while (x % y != 0)
    {
        int _x, _y, _s, _t, _u, _v;
        _x = x; _y = y; _s = s; _t = t; _u = u; _v = v;
        
        x = _y;
        y = _x % _y;
        s = _u - _s * (_x / _y);
        t = _v - _t * (_x / _y);
        u = _s;
        v = _t;
    }
    
    while (s < 0)
    {
        s += b;
    }
    
    out << s << "\n";
    
    in.close();
    out.close();
    
    return 0;
}