#include<fstream>
using namespace std;ifstream f("inversmodular.in");ofstream g("inversmodular.out");int a,n;void e(long long&x,long long&y,int a,int b){if(b==0)x=1,y=0;else{e(x,y,b,a%b);long long c=x;x=y;y=c-y*(a/b);}}int main(){f>>a>>n;long long x=0,y=0;e(x,y,a,n);if(x<=0)x=n+x%n;g<<x;}