#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>using namespace std;typedef long long LL;LL gcd(LL a,LL b){    return b==0?a:gcd(b,a%b);}void kzgcd(LL a,LL b,LL& d,LL& x,LL& y){    if (!b)    {        d=a;x=1;y=0;    }    else    {        kzgcd(b,a%b,d,y,x);        y-=x*(a/b);    }}LL inv(LL a, LL n){    LL d,x,y;    kzgcd(a,n,d,x,y);    return d==1?(x+n)%n:-1;}int main(){    long long aa,nn;    cin>>aa>>nn;    long long ans=inv(aa,nn);    cout<<ans;}