#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

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

/// A>=1 si N>=2 doua numere naturale
/// 1<=A<=N-1 cu (A,N)=1 prime intre ele
/// 1<=X<=N-1 inversul modular => A*X congruent cu 1 modulo N

ll A, N, x, y, aux;

void euclid(ll a, ll b)
{
    if(b==0){
        x=1;
        y=0;
        return;
    }
    euclid(b,a%b);
    aux=x;
    x=y;
    y=aux-a/b*y;
}

int main()
{
    fin>>A>>N;
    euclid(A,N);
    if(x<0)
        x=N+x%N;
    fout<<x;

    fin.close();
    fout.close();
    return 0;
}