#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

void gcd(int64_t &x, int64_t &y, int a, int b)
{
     if(!b)
         x=1, y=0;
     else
     {
         gcd(x, y, b, a % b);
         int64_t aux=x;
         x=y;
         y=aux-y*(a/b);
     }
}

int a, n;
int64_t inv, ins;

int main()
{
    int a, n, x, y, d;
    fin>>a>>n;
    gcd(inv, ins, a, n);
    if(inv<=0)
        inv=n+inv%n;
    fout<<inv;
    return 0;
}