#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
///folosim algoritmul lui Euclid extins
///gasim coeficinetii x si y ( ne gandim la a*x+b*y=1, avem a,b,c din cerinta, deci putem afla x si y)
///luam coeficientul lui a, deoarece trebuie sa gasim inversul modular al primului termen
///algoritmul intoarace valori intre -b si b, de aceea putem adauga doar o data b si totul e rezolvat (la if)
int egcd(int a, int b, int &x, int&y)
{
    if(b==0)
    {
     x=1;
     y=0;
     return a;
    }
    int d,X,Y;
   d=egcd(b,a%b,X,Y);
   x=Y; y=X-(a/b)*Y;
   return d;
}
int main()
{
    int a,b,d,x,y;
    fin>>a>>b;
    d=egcd(a,b,x,y);
    if(x<0)
    {
        x+=b;
    }
    fout<<x%b;
    return 0;

}