#include <iostream>
#include <fstream>

using namespace std;

void find(long long a, long long b, long long *x, long long *y){
	if(b == 0){
		*x = 1;
		*y = 0;
		 
	} else {
	long long x0, y0;
	find(b, a%b, &x0, &y0);
	*x = y0;
	*y = x0 - (a/b)*y0;
   }

}

int main(){
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
    long long A, N;
    fin >> A >> N;
    long long x = 0, y;
    find(A, N, &x, &y);
    if(x<=0){
       x = N + x%N;
    }

    fout << x <<'\n';
    return 0;
}