#include <fstream>

using namespace std;

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

void egcd(int a,int b,int* d,int *x,int *y){

    if(!b){
        *d=a;
        *x=1;
        *y=0;
    }else{
        int x0,y0;
        egcd(b,a%b,d,&x0,&y0);
        *x=y0;
        *y=x0+(-a/b)*y0;
    }

}

int main()
{
    int a,n;

    f>>a>>n;

    int x,y,d=1;

    egcd(a,n,&d,&x,&y);

    if(x<=0)
        x=n+x%n;
    g<<x;

    return 0;
}









/*#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct nod{
    nod(int a,int b):nr(a),price(b){}
    int nr,price;
};

struct cmp{bool operator() (const nod &m1,const nod &m2) {return m1.price>m2.price;}};

int main()
{
    int n,m,st,sf;

    f>>n>>m>>st>>sf;

    vector<int> v[1001],cs[1001];

    for(int i=1;i<=m;i++){
        int x,y,pr;
        f>>x>>y>>pr;

        v[x].push_back(y);
        v[y].push_back(x);
        cs[x].push_back(pr);
        cs[y].push_back(pr);
    }

    int ds[1001]={};

    for(int i=1;i<=n;i++)
        ds[i]=1000000000;
    ds[st]=0;

    priority_queue<nod,vector<nod>,cmp> pq;

    pq.push(nod(st,0));

    while(!pq.empty()){
        nod ax=pq.top(); pq.pop();
        if(ax.price>ds[ax.nr])
            continue;
        int x=ax.nr;

        for(unsigned j=0;j<v[x].size();j++)
            if(cs[x][j]+ds[x]<ds[v[x][j]]){
                ds[v[x][j]]=cs[x][j]+ds[x];
                pq.push(nod(v[x][j],ds[v[x][j]]));
            }
    }

    unsigned long long nr[1001]={},nrs=0;
    nr[st]=1;

    queue<int> q;
    q.push(st);

    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(unsigned j=0;j<v[x].size();j++)
            if(ds[v[x][j]]==ds[x]+cs[x][j]){
                nr[v[x][j]]+=nr[x];
                q.push(v[x][j]);
            }
    }

    g<<nr[sf];

    return 0;
}*/