#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;
}