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

void euclid(int a, int b, ll &x, ll &y)

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

int main()
{
    int 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;
}