#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)

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

    int x0,y0;
    ExtendedGCD(b,a%b,d,x0,y0);

    int c = a/b;

    x = y0;
    y = x0 - y0*c;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");

    int A,N;
    fin >> A >> N;
    
    int d,x,y;
    ExtendedGCD(A,N,d,x,y);

    while (x < 0) x += N;
    
    fout << x;
}