#include <cstdio>
using namespace std;
int a,n;
long long inv, ins;
void gcd(long long &x, long long &y, int a, int b)
{
    if(!b) x=1, y=0;
    else
    {
        gcd(x, y, b, a%b);
        long long aux = x;
        x = y;
        y = aux-y*(a/b);
    }
}
int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d %d", &a, &n);
    gcd(inv, ins, a, n);
    if(inv <= 0) inv = n+inv%n;
    printf("%lld", inv);
    return 0;
}