#include <iostream>
#include <cstdio>

using namespace std;

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

int main()
{
    long long x = 0 , y ;
    int a , n ;
    freopen( "inversmodular.in" , "r" , stdin ) ;
    freopen( "inversmodular.out" , "w" , stdout ) ;
    scanf( "%d %d" , &a , &n ) ;
    euclid( a , n , x , y ) ;
    if ( x < 0 )
        x = n + x % n ;
    printf( "%lld\n" , x ) ;
    return 0;
}