#include <bits/stdc++.h>

#define ll long long

std::ifstream InFile("inversmodular.in");
std::ofstream OutFile("inversmodular.out");

ll A, N;

void Euclid(ll a, ll b, ll &X, ll &Y) {
    if (b==0) {
        X = 1;
        Y = 0;
        return;
    }   Euclid(b, a%b, X, Y);

    ll aux = Y;
    Y = X - (a/b)*Y;
    X = aux;
}

void Citire() {
    InFile >> A >> N;
}

void Rezolvare() {
    ll Aux, Inv;
    Euclid(A, N, Inv, Aux);

    if (Inv <= 0) Inv = Inv + Inv%N;

    OutFile << Inv << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}