#include<bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;

    return d;
}

int main()
{
    int a, b;
    cin >> a >> b;
    int x, y;
    exgcd(a, b, x, y);
    cout << (x % b + b) % b << endl;
    return 0;
}

/*
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

扩展欧几里得用来求 ax + by = gcd(a, b) 的解
当b == 0时， ax + by = a 故此时 x = 1, y = 0
当b != 0时
因为 gcd(a, b) = gcd(b, a % b)
而 bx' + (a % b)y' = gcd(b, a % b);
=> bx' + (a - a / b * b) y' = gcd(b, a % b)
=> ay' + b(x' - a / b*y') = gcd(b, a % b) = gcd(a, b);

x = y'   y = (x' - a / b*y)

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int x1, y1, gcd;
    gcd = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return gcd;
}

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}


对于一般方程 ax + by = c

设d = gcd(a, b) 则其有解当且仅当d | c 时
所以我们一般求出ax + by = gcd(a, b)的解  x0 y0
此时该方程的一个特解为：x' = x0*c/d y' = y0*c/d 

通解 = 特解 + 齐次解
齐次解  ax + by = 0的解
通解： x = x' + k*b / d   y = y' - k*a/d  k为自然数

通解的最小非负整数解为：设t = b/d  (x' % t + t) % t;

(x % b + b) % b 
本题  ax=b(mod m)
ax = m*(-y) + b;
ax + my = b



-----
ax=b(mod m)
ax = m*(-y) + b;
ax + my = b
当b = 1时 a和m互质时，所求的x即为a的逆元
*/

/*

ax % b = 1 => ax + by = 1;
x = x' + kb;
y = y' - ka;
t = b / 1 = b;
(x'% b + b) % b;

*/