#include<cstdio>
#define ll long long

ll x , y , n , a ;
inline void invmodular( ll a , ll n , ll *x , ll *y)
{
	if ( n == 0 )
	{
		*x = 1 ;
		*y = 0 ;
	}
	else
	{
		ll x0 , y0 ;
		invmodular( n , a%n , &x0 , &y0 );
		*x = y0;
		*y= x0-(a/n)*y0 ;
	}
}

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

	scanf(" %lld %lld ", &a, &n );
	invmodular ( a , n , &x , &y );

	while ( x < 0  ) x += n; 

	printf ( "%lld\n" , x ) ;

	

	return 0 ;
}