#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define pb push_back
#define FASTIO ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

#define pii pair<int , int>
#define sz(a) ((int)((a).size()))
const int MAX = 1e4 + 1;
int a,n;
void gcd(LL &x , LL &y , int a, int n)
{
    if(!n)
        x = 1 , y = 0;
    else
    {
        gcd(x,y,n,a%n);
        int aux = x;
        x = y;
        y = aux - y*(a/n);
    }
}
LL x,y;
int32_t main()
{
    FASTIO;
    f>>a>>n;
    gcd(x,y,a,n);
    while(x<=0)
    {
        x = n + (x % n);
    }
    g<<x;
}