#include<stdio.h>

void gcd(long long  &x, long long &y, int a, int b) 
{ 
     if (!b) 
         x = 1, y = 0; 
     else 
     {            
         gcd(x, y, b, a % b);
         long long aux = x;
         x = y;
         y = aux - y * (a / b);
     }
}

int main(){
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	int A, N;
	long long inv=0, ins;
	scanf("%d %d", &A, &N);
	gcd(inv, ins, A, N);
	while(inv<=0)inv=N+inv%N;
	printf("%d\n", inv);
	fclose(stdin);fclose(stdout);
}