#include <cstdio>
        #include <cmath>
        using namespace std;
        bool prim (long long int x)
        {
            int i;
            for (i=2; i*i<=x; i++)
                if (x%i==0) return false; return true;
        }
        int sol (long long int nr)
        {
            long long int i, x=nr;
            for (i=2; i*i<=nr; i++)
            {
                if (nr%i==0)
                {
                    while (nr%i==0) nr/=i;
                    x=(x/i)*(i-1);
                }
            }
            if (nr!=1) x=(x/nr)*(nr-1);
            return x;
        }
        int main()
        {
            long long int a, n, i;
            freopen("inversmodular.in","r",stdin);
            freopen("inversmodular.out","w",stdout);
            scanf("%lld%lld",&a,&n);
            if (prim(n))
            {
                long long int put=sol(n)-1, nr=a, x=1, p;
                for (p=1; p<=put; p<<=1)
                {
                    if (p&put) x=(x*nr)%n;
                    nr=(nr*nr)%n;
                }
                printf("%lld",x);
            }
            else printf("-1");
            fclose(stdin);
            fclose(stdout);
            return 0;
        }