#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define nozerous(x) (x & -x)
#define MOD 1000000007
#define M_PI           3.14159265358979323846
#define EPS 0.00001
using namespace std;
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = (1 << 30), NMAX(10005), VMAX(1000000);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;
using ll = long long;
using cd = complex<double>;
const double PI = acos(-1);
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}
ll gcdExtins(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll x0, y0;
    ll d = gcdExtins(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}
int main()
{
    BUNA("inversmodular");
    ll a, n;
    cin >> a >> n;
    ll x, y;
    gcdExtins(a, n, x, y);
    if(x <= 0)
        x = (x + n) % n;
    cout << x << '\n';
    PA();
}