#include <iostream>
#include <fstream>
using namespace std;

ifstream F("inversmodular.in");
ofstream G("inversmodular.out");

int a,n;

void euclid(int a,int &x,int b,int &y,int c)
{
    if ( b == 0 )
    {
        x = 1;
        y = 0;
        return;
    }

    int x0 = 0, y0 = 0;
    euclid(b,x0,a%b,y0,c);

    x = y0;
    y = x0 - (a/b) * y0;
}

int inv(int a,int b)
{
    int c = 1; // cmmdc(a,n) = 1
    // ax + by = c

    int x = 0, y = 0;
    euclid(a,x,b,y,c);

    return x;
}

int main()
{
    F>>a>>n;
    G<<inv(a,n)<<'\n';
}