#include <iostream>
#include <fstream>
#define ll long long int
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
ll gcd( ll a, ll b, ll &x, ll &y)
{
    if(!b){ x=1;y=0; return a;}
    ll x0,y0;
    ll d=gcd(b,a%b,x0,y0);
    x=y0;
    y=x0-(a/b)*y0;
    return d;
}
int main()
{
    ll a,n;
    fin>>a>>n;
    ll x=0,y=0;
    ll ans=gcd(a,n,x,y);
    while(x<0) x+=n;
    fout<<x<<"\n";
    return 0;
}