#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>

struct pair {
	long x, y;
	
	pair(long _x, long _y) : x(_x), y(_y) {}
};

void print(pair p)
{
	std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}

void printGcd(pair p, long a, long b)
{
	std::cout << "GCD is " << a * p.x + b * p.y << std::endl;
}

pair euclid(long a, long b)
{	
	pair prev(1, 0);
	pair curr(0, 1);
	
	while(b != 0)
	{		
		long q = a / b;
		long r = a % b;
		
		pair old = curr;
		
		curr.x = prev.x - q * curr.x;
		curr.y = prev.y - q * curr.y;
		prev = old;
		
		a = b;
		b = r;
	}
	
	return prev;
}

int main(int argc, char ** argv)
{
	std::ifstream fin("inversmodular.in");
	std::ofstream fout("inversmodular.out");
	
	if(!fin || !fout)
		return -1;
	
	unsigned long a, n;
	fin >> a >> n;
	
	pair result = euclid(n, a);
	
	if(result.y > 0)
		fout << result.y;
	else
		fout << n + result.y;
	
	return 0;
}