#include <cstdio>
using namespace std;

int a,n,x, y;

void euclid( int a, int b, int &x, int &y ) {
	if ( b==0 ) {
		x = 1, y = 0;
		return ;
	}
	int x0, y0, c = a/b;
	euclid( b, a%b, x0, y0 );
	x = y0;
	y = x0 - c * y0;
}

int main() {
	freopen( "inversmodular.in", "r", stdin );
	freopen( "inversmodular.out", "w", stdout );

	scanf( "%d %d", &a, &n );
	euclid( n, a, x, y );
    while ( y < 0 ) y += n;
	printf("%d\n", y);
	return 0;
}