#include <cstdio>
using namespace std;

bool prim( int n ){

    if( n % 2 == 0 || n <= 1 ) return false;
    int i;

    for( i = 3; i * i <= n; i += 2 )
        if( n % i == 0 ) return false;

    return true;
}

int euler( int n ){

    int i, j, t, d, ok;

    d = 1;
    i = 2;

    if( prim(n) ) return n - 1;

    while( n > 1 ){
        t = 1;
        ok = 0;

        while( n % i == 0 ){
            n /= i;
            t *= i;
            ok = 1;
        }

        if( ok ) d *= ( i - 1 ) * (t / i);
        i++;
    }

    return d;


}


long long dei( int a, int b, int c ){

    if( b == 1 ) return a % c;
    else{
        long long k = dei( a, b / 2, c ) % c;
        if( b % 2 == 0 ) return k*k % c;
        else return (a % c)* dei(a,b-1,c) % c;
    }


}



int main()
{

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


    int a, x, t;

    scanf("%d%d",&a,&x);

    t = euler( x );

    printf("%lld",dei( a, t-1, x ));


    return 0;
}