#include <stdio.h>

void euclid(int a, int b, int* x, int* y);
int invmod(int a, int n);

int main(){
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	int a, n;
	scanf("%d%d", &a, &n);
	printf("%d\n", invmod(a, n));
	return 0;
}

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

int invmod(int a, int n){
	int x, y;
	euclid(a, n, &x, &y);
	while(x < 0)
		x += n;

	return x % n;
}