#include <iostream>
#include <cstdio>

using namespace std;

long long a, n;

pair<long long, long long> euclidext(long long a, long long b)
{
    if(b==0)
        return {1,0};
    auto p=euclidext(b, a%b);
    return {p.second, p.first-(a/b)*p.second};
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%lld %lld", &a, &n);
    pair<long long, long long> rez=euclidext(a, n);
    long long int k=rez.first;
    while(k<0)
        k+=n;
    printf("%lld", k);
    return 0;
}