#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
int a,n;
int gcdext(int a, int b, int &x, int &y){
    int s1=a, s2=b, s3;
    int a1=1, a2=0, a3;
    int b1=0, b2=1, b3;
    while (s2!=0){
        s3=s1%s2;
        a3=a1-(s1/s2)*a2;
        b3=b1-(s1/s2)*b2;
        s1=s2; a1=a2; b1=b2;
        s2=s3; a2=a3; b2=b3;
    }
    x=a1;
    y=b1;
    return s1;
}
int main()
{
    fin>>a>>n;
    int x,y;
    gcdext(a,n,x,y);
    if (x<0){
        x+=(-x/n+1)*n;
    }
    fout<<x;
    //cout<<(-7)/7;
    return 0;
}