#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

ll euclid (ll a, ll b, ll &x, ll &y) {
    if (b==0) {
        x=1; y=0;
        return a;
    }
    else {
        ll x1, y1;
        ll d = euclid(b, a%b, x1, y1);
        ll q = a/b;
        /* 
        x1*b+y1*(a%b)==d 
        a = q*b+r ==> r == a-q*b
        x1*b + y1*(a-q*b) == d
        x1*b + y1*a - y1*q*b == d
        a*y1 + b*(x1-q*y1) == d
        */
        x = y1;
        y = x1-q*y1;
        return d;
    }
}

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    ll a, n, x, y;
    fin>>a>>n;
    ll d = euclid(a, n, x, y);
    while (x<0) x+=n;
    fout<<x;
    return 0;
}