#include <stdio.h>
#include<fstream>
using namespace std;

#define ll long long
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int n, a;

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

int main()
{
    ll inv = 0, ins;

    fin >> a >> n;
    cmmdc(a, n, inv, ins);

    if (inv <= 0)
       inv = n + inv % n;
    fout << inv << ' ';

    return 0;
}