#include <bits/stdc++.h>
#define z(x) (x & (-x))
typedef long long ll;
using namespace std;

ll a, n;

void gcd(ll a, ll b, ll &x, ll &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
    }else
    {
        gcd(b, a % b, x, y);
        ll tmp = x;
        x = y;
        y = tmp - a / b * y; 
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
	cin >> a >> n;
	ll x = 0, y;
	gcd(a, n, x, y);
	cout << (x > 0 ? x : x + n + x % n);
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}