#include<fstream>
#define INfile "inversmodular.in"
#define OUTfile "inversmodular.out"

using namespace std ;

ifstream f ( INfile ) ;
ofstream g ( OUTfile ) ;

int A , N , x , y ;

void invmod ( int & x , int & y , int A , int N ) ;

int main ()
{
	f >> A >> N ;
	invmod ( x , y , A , N ) ;
	
	if ( x < 0 ) 
		x = N + x % N ;
	g << x ; 
	f.close () ;
	g.close () ;
}

void invmod ( int & x , int & y , int A , int N ) 
{
	if ( N == 0 )
	{ x = 1 ; y = 0 ; } 
	else 
	{
		int x0 , y0 ; 
		invmod ( x0 , y0 , N , A % N ) ;
		x = y0 ;
		y = x0 - ( A / N ) * y0 ;
	}
}