#include <fstream>
#define lint long long int

using namespace std;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

lint a,n,x;

lint Rid(lint ba,lint ex)
{
    lint re=1;
    while(ex)
    {
        if(ex&1)
            re=(re*ba)%n;

        ex>>=1;
        ba=(ba*ba)%n;
    }

    return re;
}

int EulersdPhi(lint n)
{
    lint pr=n;
    x=n;

    for(int i=2;i*i<=n;++i)
        if(x%i==0)
        {
            while(!(x%i))
                x/=i;
            pr=1LL*pr*(i-1)/i;
        }

    if(x!=1)
        pr=1LL*pr*(x-1)/x;

    return pr;
}

int main()
{
    cin>>a>>n;

    x=Rid(a,EulersdPhi(n)-1);

    cout<<x;

    return 0;
}