// https://infoarena.ro/problema/inversmodular

#include <iostream>
#include <fstream>

using namespace std;

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

void greatest_common_divisor(long long int &x, long long int &y, int a, int n);

int main(){
    long long int inv = 0, ins = 0;  
    int a, n;
    
    fin >> a >> n;

    greatest_common_divisor(inv, ins, a, n);

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

    fout << inv;

    fin.close();
    fout.close();
    return 0;
}

void greatest_common_divisor(long long int &x, long long int &y, int a, int n)
{  
    if (n == 0) {
        x = 1;
        y = 0;  
    }
    else {             
        greatest_common_divisor(x, y, n, a % n);
        long long int aux = x;
        x = y;
        y = aux - y * (a / n);
    }
}