#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long a,n;
long long it=1;
long long euclid(long long a,long long b, long long& x, long long& y)
{
    if(b%a==0)
    {
        x=1;
        y=0;
        return a;
    }
    long long cat=b/a;
    it++;
    b=b%a;
    long long nx,ny;
    long long rez=euclid(b,a,nx,ny);
    x=ny-cat*nx;
    y=nx;
    return rez;
}
int main()
{
    in>>a>>n;
    long long x,y;
    if(a>n)
    {
        swap(a,n);
    }
    long long d=euclid(a,n,x,y);
    out<<((long long)(x+n))%n;
}