#include <bits/stdc++.h>
//#define N 100
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

//////int ct,a[N][N],xs,ys,xf,yf,n,m;
//////
//////
//////
//////void Citire()
//////{
//////    fin >> n >>m;
//////    for(int i=1;i<=n;i++)
//////        for(int j=1;j<=m;j++)
//////            fin >>a[i][j];
//////    fin >> xs >> ys;
//////    fin >> xf >> yf;
//////    fin.close();
//////    for(int i=1;i<=n;i++)
//////        a[i][0]=a[i][m+1]=1;
//////    for(int i=1;i<=m;i++)
//////        a[0][i]=a[n+1][i]=1;
//////}
//////
//////int dl[4]={0,0,1,-1};
//////int dc[4]={1,-1,0,0};
//////
//////
//////void Gen(int x,int y)
//////{
//////    if( x==xf and y==yf )
//////        ct++;
//////    else
//////    {
//////        a[x][y]=1;
//////        for(int i=0;i<4;i++)
//////        {
//////            int xc,yc;
//////            xc=x+dl[i];
//////            yc=y+dc[i];
//////            if( a[xc][yc]==0 )Gen(xc,yc);
//////        }
//////        a[x][y]=0;
//////    }
//////
//////}
//////

void Euclid(int a,int b,int&x,int&y)
{
    if( b==0 )x=y=1;
    else
    {
        int x1,y1;
        Euclid(b,a%b,x1,y1);
        x=y1;
        y=x1-a/b*y1;
    }
}

int Invers_Mod(int a,int b)
{
    int x,y;
    Euclid(a,b,x,y);
    while(x<0)x+=b;
    return x;
}

int main()
{
    int n,a;
    fin >> a >> n;
    fout << Invers_Mod(a,n);






//////    map<int,int> M,N;
//////    M[8]=12;
//////    M[2]=432;
//////    M[2]=32;
//////    N[2]=60;
//////    for(auto i:N)
//////        cout << i.first << "  " << i.second << "\n";
////
//////    multiset<int>s;
//////    s.insert(5);
//////    s.insert(5);
//////    s.insert(5);
//////
//////    multiset<int>::iterator it=s.begin();
//////
//////    for(;it<s.end();it++)
//////        cout << *it << " ";


//////    Citire();
//////    for(int i=0;i<=n+1;i++,cout << "\n")
//////        for(int j=0;j<=m+1;j++)
//////            cout << a[i][j] << " ";
//////
//////
//////    Gen(xs,ys);
//////    fout << ct << "\n";
//////    fout.close();
    return 0;
}