#include <bits/stdc++.h>
#define SL signed long
using namespace std;
 ifstream fin("inversmodular.in");
 ofstream fout("inversmodular.out");

SL a,n;

void euclid(SL a ,SL b ,SL &x ,SL &y )
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        SL X,Y;
         euclid(b ,a%b ,X,Y );
         x = Y;
         y = X-(a / b) * Y;
    }
}

int main()
{
    fin >> a >> n;
    SL x,y;

     euclid(a ,n ,x ,y );
     if (x <= 0)
         x = n + x%n;

    fout << x;
    return 0;
}