#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

void open(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
}
typedef long long ll;
ll a,n,x,y,fpb;

/*ll bigmod(ll a,ll b){
    if (b==0) return 1;
    if (b==1) return a%n;
    if (b%2==0){
        ll x=bigmod(a,b/2);
        return (x*x)%n;
    }
    return (a*bigmod(a,b-1))%n;
}*/

ll gcd(ll a,ll b,ll &x,ll &y){
    if (b==0){
        x=1;
        y=0;
        return a;
    }
    ll x0,y0,tmp;
    tmp=gcd(b,a%b,x0,y0);
    x=y0;
    y=x0-(a/b)*y0;
    return tmp;
}

int main(){
    open();
    scanf("%lld%lld",&a,&n);
    /*  n= prime
    *   a*x=1(mod n)
    *   x=1/a(mod n)
    *   modular inverse= (1 * a^n-2)%n
    *   mark 60
    */
    //printf("%lld\n",bigmod(a,n-2));
    fpb=gcd(a,n,x,y);
    if (x<=0){
        x=n+x%n;
    }
    printf("%d\n",x);
    return 0;
}