#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;
        }
        void euclid (long long int a, long long int b, long long int &x, long long int &y)
        {
            if (b==0)
            {
                x=1; y=0;
            }
            else
            {
                euclid(b,a%b,x,y);
                long long int aux;
                aux=x;
                x=y;
                y=aux-y*(a/b);
            }
        }
        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
            {
                long long int x=0, y;
                euclid(a,n,x,y);
                if (x<=0) x=n+x%n;
                printf ("%lld",x);
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }