#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int x,y;
int a,n;

void euclid_extins(int a, int b) {
    if (b!=0) {
        euclid_extins(b,a%b);
    }
    if (b==0) {
        x = 1;
        y = 0;
    }
    else {
        int aux = y;
        y = x - (a/b)*y;
        x = aux;
    }
}

int main()
{
    f >> a >> n;
    euclid_extins(a,n);
    if (x<1) {
        x += -((x/n)-1)*n;
    }
    g << x;
    return 0;
}