#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long invers,y,a,n;
void inv(long long &x,long long &y,int a,int b){
         if(b==0){
            x=1;
            y=0;
         }
         else
         {
             inv(x,y,b,a%b);
             long long sup=x;
             x=y;
             y=sup-y*(a/b);
         }
                                               }
int main()
{
        fin>>a>>n;
        inv(invers,y,a,n);
        if(invers<=0)
           invers=n+invers%n;
           fout<<invers;
    return 0;
}