#include <iostream>
#include <cstdio>
using namespace std;
pair<long long,long long> euclidExtins(long long a,long long b)
{
    if(!b)
        return make_pair(1,0);
    pair<long long,long long> p=euclidExtins(b,a%b);
    return make_pair(p.second,p.first-p.second*(a/b));
}
int main()
{

    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    long long a,b;
    scanf("%lld%lld",&a,&b);
    long long rez=euclidExtins(a,b).first;
    while(rez<0)
        rez+=b;
    printf("%d",rez);

    return 0;
}