#include<fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int a,n,invsmod,k;
void euclid( int a, int b, int &x, int &y ){
    if( b == 0 ){
        x = 1;
        y = 0;
    }else{
        int x1 = 0,y1 = 0;
        euclid( b, a%b, x1, y1 );
        x = y1;
        y = x1 - a/b * y1;
    }
}
int main(){
    cin >> a >> n;
    euclid(a,n,invsmod,k);
    while( invsmod <= 0){
        invsmod += n;
    }
    cout << invsmod;
    return 0;
}