#include<fstream>
using namespace std;
long long a,n;
int x,i;
int main ()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    fin>>a>>n;
    x=a%n;
    for(i=1;i<=n-1;i++)
    {
        if((x*i)%n==1)
        {
            fout<<i;
            i=n;
        }
    }
    fin.close();
    fout.close();
    return 0;
}