#include<fstream>
using namespace std;
ifstream  fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n,x,y,d;
int euclid_extins(int a, int b, int &x, int &y){
    int d,x0,y0;
    if(b==0){
        x=1;y=0;return a;
    }
    d=euclid_extins(b,a%b,x0,y0);
    x=y0;
    y=x0-y0*(a/b);
    return d;
}

int main(){
    fin>>a>>n;
    d=euclid_extins(a,n,x,y);
    ///x este solutia
    ///deoarece x poate fi <=0 trebuie adunat un multiplu de n astfel incat suma dintre x si n sa fie cuprinsa intre 1 si n-1
    if(x<=0){
        x=n+x%n;
        ///deoarece x%n este negativ dar in modul mai mic decat impartitorul n
    }
    fout<<x;
    fout.close();
    fin.close();
    return 0;
}