#include <cstdio>
using namespace std;

void euclidext(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    int x1, y1;
    euclidext(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
}
int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int n;
    int a;
    int x, y;
    scanf("%d %d", &n, &a);
    euclidext(a, n, x, y);
    while(x<0)
        x=x+n;
    printf("%d", x);

    return 0;
}