#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

int A, N ;

int D, x, y ;

int gcd(int a, int b, int &x, int &y)
{
    if( b == 0 )
    {
        x = 1 ;
        y = 0 ;
        return a ;
    }
    else
    {
        int x0, y0, D ;
        D = gcd( b, a % b, x0, y0 ) ;

        x = y0 ;
        y = x0 - ( a / b ) * y0 ;

        return D ;
    }
}

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

    scanf("%d%d", &A, &N);

    D = gcd( A, N, x, y ) ;

    while( x < 0 )
        x += N ;

    printf("%d", x);

	return 0 ;
}