#include <bits/stdc++.h>
#define MOD 100007
#define ll long long
using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
long long n,k,inv,y;
void gcd(ll &x, ll&y , ll a,ll b)
{
    if(b==0) x=1,y=0;
    else
    {
        gcd(x,y,b,a%b);
        ll ax=x;
        x=y;
        y=ax-y*(a/b);
    }
}
int main()
{
    f>>n>>k;
    gcd(inv,y,n,k);
    if(inv<=0) inv+=k;
    g<<inv;
    return 0;
}