#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

#define ll long long
#define ui unsigned int
#define pb push_back
const int NMax = 2e5 + 5;

ll A,N;

ll euclid(ll,ll,ll&,ll&);

int main() {
    in>>A>>N;

    ll x,y,d;

    // folosind algoritmul lui euclid extins
    // se gasesc doua numere x,y astfel incat
    // x*A + y*N = (A,N), adica
    // x*A + y*N = 1
    // ceea ce inseamna ca x este inversul modular al lui A
    d = euclid(A,N,x,y);

    while (x < 0) {
        x += N;
    }
    out<<x % N<<'\n';

    in.close();out.close();
    return 0;
}

ll euclid(ll a,ll b,ll& x,ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    ll x0,y0,d;
    d = euclid(b,a%b,x0,y0);
    x = y0;
    y = x0 - (a/b) * y0;

    return d;
}