#include <iostream>
using namespace std;

void euclid ( int a, int b, int& x, int& y)
{
    if ( b == 0)
    {
        x = y = 1;
    }
    else
    {
        int x0, y0;
        euclid(b, a % b, x0, y0);
        x = y0;
        y = x0 - a / b * y0;
    }
}

int main()
{
    int num, mod;
    cin >> num >> mod;

    int ans, numar;
    euclid(num, mod, ans, numar);

    while ( ans < 0) ans += mod;
    cout << ans;

    return 0;
}