#include <bits/stdc++.h>



using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int a,n;

void Euclid_Extins(int a,int b,int&x,int&y)
{
    if(b==0)x=y=1;
    else
    {
        int x1,y1;
        Euclid_Extins(b,a%b,x1,y1);
        x=y1;
        y=x1-a/b*y1;
    }
}
//void euclid(int a , int b ,int & x ,int & y)
//{
//    if(b == 0)
//    {
//        x = 1, y = 1;
//    }
//    else
//    {
//        int x1 , y1;
//        euclid(b , a % b , x1 , y1);
//        x = y1;
//        y = x1 - a / b * y1;
//    }
//}


int Invers_Modular()
{
    int x,y;
//    euclid(a,n,x,y);
    Euclid_Extins(a,n,x,y);
    while(x<0)x+=n;
    return x;
}

int main()
{
    fin >> a >> n;
    fout << Invers_Modular();


    return 0;
}