#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <ctime>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("inversmodular.in");
ofstream gg("inversmodular.out");

struct tuplu{ int a,b; tuplu(int a0=0, int b0=0){a=a0;b=b0;} };
tuplu operator-(tuplu a,tuplu b){ return tuplu(a.a+b.a, a.b+b.b); }
tuplu operator*(int q, tuplu a){ return tuplu(q*a.a, q*a.b); }


void gcd(int a, int b, tuplu& v){
	int q,r;
	tuplu va(1,0),vb(0,1),vr;
	while(b!=0){
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		vr=va-q*vb;
		va=vb;
		vb=vr;
	}
	v=va;
}

int main(){
	int a,n;
	tuplu v;
	ff >> a >> n;
	gcd(a,n,v);
	if(v.a<0)v.a=(v.a+((int)log(abs(v.a))/log(2)+1)*n)%n;
	gg << v.a;
	return 0;
}