#include <bits/stdc++.h>
#define ll long long
FILE *fin=freopen("inversmodular.in", "r", stdin);
FILE *fout=freopen("inversmodular.out", "w", stdout);

using namespace std;
int n, a;
void gcd(int a, int b, ll &x, ll &y)
{
    if(b == 0)
        x = 1, y = 0;
    else
    {
        gcd(b, a % b, x, y);
        ll aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
void verif(ll &x)
{
    if(x < 0)
        x += n;
}
void read()
{
    scanf("%d %d", &a, &n);
}
void solve_write()
{
    ll x = 0, y = 0;
    gcd(a, n, x, y);
    verif(x);
    printf("%d\n", x);
}

int main()
{
    read();
    solve_write();
    return 0;
}