#include <bits/stdc++.h>
using namespace std;
/// a * x + b * y = cmmdc(a,b)
int cmmdc(int a,int b,long long &x,long long &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    long long x1,y1;
    int d=cmmdc(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return d;
}
int InvMod(int A,int N){
    /// cmmdc(A,N) = 1
    /// A * x + N * y = 1
    long long inv,trash;
    cmmdc(A,N,inv,trash);
    inv=inv-N*(inv/N);
    return inv;
}
int main(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int A,N;
    cin>>A>>N;
    cout<<InvMod(A,N);
}