#include <fstream>

std::ifstream INPUT_FILE("inversmodular.in");
std::ofstream OUTPUT_FILE("inversmodular.out");


void euclid(long long a,long long b,long long &k,long long &l){
    if(!b){
        k=1;
        l=0;
        return;
    }
    long long k1,l1;
    euclid(b,a%b,k1,l1);
    k=l1;
    l=k1-(a/b)*l1;
}

int main() {
    long long A,N,x,y;
    INPUT_FILE>>A>>N;
    euclid(A,N,x,y);
    if(x<=0)x=N+x%N;
    OUTPUT_FILE<<x;
    return 0;
}