#include <iostream>
#include <fstream>

using namespace std;
int A,N;
void cmmmdc(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return ;
    }
    int y0,x0;
    cmmmdc(b,a%b,x0,y0);
    x=y0;
    y=x0-a/b*y0;
}
void rez()
{
    int x;
    int y;
    cmmmdc(A,N,x,y);
    while(x<0)
    x+=N;
    printf("%d\n",x);
}
int main()
{
        freopen("inversmodular.in","r",stdin);
        freopen("inversmodular.out","w",stdout);
        scanf("%d %d",&A,&N);
        rez();
        return 0;

}