#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n;
long long x,y;
int euler(int n)
{
    int nr=n;
    int d=2;
    if (n%2==0)
    {
        nr=nr/2*(2-1);
        while (n%2==0)
        {
            n/=2;
        }
    }
    while (n>1)
    {
        if (n%d==0)
        {
            nr=nr/d*(d-1);
            while (n%d==0)
            {
                n/=d;
            }
        }
        if (d*d<=n)
            d+=2;
        else
            d=n;
    }
    return nr;
}
void euclid(long long &x, long long &y, int a, int b)
{
    if (b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        euclid(x,y,b,a%b);
        long long aux=x;
        x=y;
        y=aux-y*(a/b);
    }
}
int lgpow(int a, int b)
{
    int p=1;
    while (b>0)
    {
        if (b%2==1)
            p=p*a;
        a=a*a;
        b/=2;
    }
    return p;
}
int main()
{
    fin >> a >> n;
    euclid(x,y,a,n);
    while (x<0)
        x+=n;
    fout << x;
    return 0;
}