#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int A,N;
struct Pair
{
    int x,y;
}P;

Pair Euclid(int a,int b,int d)
{
    Pair p,po;
    if( b == 0 )
    {
        d = a;
        p.x = 1;
        p.y = 0;
        return p;
    }
    else
    {
        po = Euclid( b, a % b, d);
        p.x = po.y;
        p.y = po.x - (a / b) * po.y;
        return p;
    }
}

int main()
{
    f>>A>>N;
    P = Euclid(A,N,1);

    while( P.x < 0 )
      P.x+=N;

    g<<P.x;

    return 0;
}