#include <cstdio>

#define ll long long

ll A, N, invers, vaux;

inline void Euclid( ll &X, ll &Y, ll a, ll b )
{
	if( !b )
		X = 1, Y = 0;
	else
	{
		Euclid( X, Y, b, a%b );
		ll aux = X;
		X = Y;
		Y = aux - Y*(a / b);
	}
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	
	scanf("%lld%lld", &A, &N);
	Euclid( invers, vaux, A, N );
	
	if( invers <= 0 )
		invers = N + invers%N;
	printf("%lld\n", invers);
	
	return 0;
}