#include <iostream>
#include <fstream>
#define ll unsigned long long
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
ll
 euclid(ll a, ll b, ll &x, ll &y)

{
    if (b == 0)
        x = 1,y = 0;
        else
        {
    euclid(b, a % b,x,y);
    ll aux = x;
    x = y;
    y = aux - (a / b) * y;
        }
}

int main()
{
    ll a,n;

        f>>a>>n;
        ll x = 0,y;
         euclid(a,n,x,y);
        while(x<=0)
            x = n + x%n;
        g<<x;


    return 0;
}