#include <bits/stdc++.h>
#define ll long long

using namespace std;

// Function for extended Euclidean Algorithm
void gcdExtended(int a, int b, ll *x, ll *y) {
    // Base Case
    if (a == 0) {
        *x = 0;
        *y = 1;
        return;
    }

    ll x1, y1; // To store results of recursive call
    gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive call
    *x = y1 - (b/a) * x1;
    *y = x1;
}

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

    ll x, y;
    int a, b;

    scanf("%d %d", &a, &b);
    /* a * x "congruent cu" 1 mod b
    <=> a * x - 1 = b * y
    <=> a * x - b * y = 1

    ecuatia are sol daca gcd(a, b) = 1,
    iar problema garanteaza ca a si b sunt coprime */

    gcdExtended(a, b, &x, &y);

    /* x poate sa fie si negativ,
    deci trebuie sa adaugam b la x pana redevine pozitiv */
    if (x <= 0)
        x = b + x % b;

    printf("%d\n", x);
    return 0;
}