using namespace std;
#include<iostream>
#include<fstream>
#include<vector>

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

long long A, N;
void cmmdc(long long &x, long long&y, long long a, long long b) { //a*x + b*y = 1 -> x este inversul modular (1/a)%b
    if (!b) {
        x = 1, y = 0;
    } else {
        cmmdc(x,y,b,a%b);
        long long aux = x;
        x = y;
        y = aux - y*(a/b);
    }
}

int main() {

    fin >> A >> N;
    long long inv = 0, helper;
    cmmdc(inv, helper, A, N);

    if (inv <= 0) {
        inv = (inv + N) % N;
    }
    fout << inv << '\n';

    return 0;
}