#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

pair <ll, ll> euclidExtins(int a, int n)
{
    if(n == 0)
        return {1, 0};
    auto p = euclidExtins(n, a%n);
    return {p.second, p.first - (a/n)*p.second};
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a, n;
    scanf("%d%d", &a, &n);
    auto p = euclidExtins(a, n);
    if(p.first >= 0)
        printf("%lld", p.first);
    else
    {
        while(p.first < 0)
            p.first+=n;
        printf("%lld", p.first);
    }
    return 0;
}