#include<fstream>
using namespace std ;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int b, n ;

int x, y ;

void euclid(int a, int b, int &x, int &y )
{
    if( b == 0 )
    {
        x = 1 ;
        y = 0 ;
    }
    else
    {
        int x0, y0 ;
        euclid( b, a % b, x0, y0 ) ;
        x = y0 ;
        y = ( x0 - ( ( long long )( a / b ) * y0) % n ) % n ;
    }
}

int main()
{
    fin >> b >> n ;

    euclid( n, b, x, y ) ;

    y += n ;

    y %= n ;

    fout << y ;

    return 0 ;
}