//
//  main.cpp
//  Invers Modular
//
//  Created by Darius Buhai on 27/10/2018.
//  Copyright © 2018 Darius Buhai. All rights reserved.
//

#include <iostream>
#include <fstream>
using namespace std;

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

pair<long, long> euclid_extins(long a, long b)
{
    if(b==0)
        return {1, 0};
    pair<long, long> p = euclid_extins(b, a%b);
    return {p.second, p.first - (a/b)*p.second};
}


int main() {
    long a, b;
    fin>>a>>b;
    long rez = euclid_extins(a, b).first;
    while(rez<0)
        rez+=b;
    fout<<rez;
    return 0;
}