// Infoarena - Arhiva Educationala Invers Modular
// Februrie 2012 Marius Dumitran
// Algoritmul lui Euclid extins O(log (N+M))

#include<string.h>
#include<stdio.h>

	
 int euclid_extins(int a, int b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
		return a;
	}
    long long x0, y0;
    int d = euclid_extins(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
	return d;
    
}

int main() {
	
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	
	long long N, M, x, y;
	scanf("%lld %lld", &M, &N);
	euclid_extins( M, N, x, y);
	x = x + (long long) N * 1000000000;
	x = x % N;
	printf("%d\n", (int)x);
	
}