#include <bits/stdc++.h>
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define min(a,b)((a<b)?(a):(b))
#define max(a,b)((a>b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
long long a,b,n,m,x,y,d;
void euclid(long long a , long long b)
{
    if(b == 0)
    {
        d=a;
        x=1,y=1;
    }
    else
    {
        euclid(b,a%b);
        x=x-a/b*y;
        sw(x,y);
    }
}
int main()
{
in>>a>>b;
euclid(a,b);
out<<(x+b)%b;
}