#include<stdio.h>
using namespace std;
void ee (int a, int b, int &x, int &y, int &d)
{
    if (b == 0){
        x = 1;
        y = 0;
        d = a;
        return;
    }
    int q = a/b, x1, y1;
    ee(b, a - q * b, x1, y1, d);
    x = y1;
    y = x1 - q*y1;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("inversmodular.in","r");
    out = fopen ("inversmodular.out","w");
    int a, n;
    fscanf (in, "%d%d", &a, &n);
    int x, y, d;
    ee(a,n,x,y,d);
    fprintf(out,"%d", (n + x % n)%n);
    return 0;
}