#include <fstream>
	
 
	
using namespace std;
	
 
	
void euclid(int A, int B, int& x, int& y){
	
    if(B == 0){
	
        x = 1;
	
        y = 0;
	
    }
	
    else{
	
        int _x, _y;
	
        euclid(B, A % B, _x, _y);
	
        x = _y;
	
        y = _x - (A / B) * _y;
	
    }
	
 
	
}
	
 
	
int main()
	
{
	
    ifstream cin("inversmodular.in");
	
    ofstream cout("inversmodular.out");
	
         
	
    int A, N, x, y;
	
    cin >> A >> N;
	
 
	
    euclid(A, N, x, y);
	
    if(x < 0)
	
        x = x + ((x / N) + 1) * N;
	
 
	
    cout << x;
	
    
	
 
	
    cin.close();
	
    cout.close();
	
 
	
    return 0;
	
}