#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int A,N;

void euclid( int a, int b, int &x, int &y )
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    else euclid( b, a%b , x, y);

    int x1;
    x1=x;
    x=y;
    y=x1-(a/b)*y;
}
int main()
{
    f>>A>>N;
    int wanted,notwanted;
    euclid(A,N,wanted,notwanted);
    wanted=wanted%N;
    while(wanted<0)
        wanted+=N;
    g<<wanted;
}