#include <stdio.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <limits.h>
#include <algorithm>
#include <deque>
#define nmax 10000010
#define mod 1999999973
using namespace std;
int a,n,x,y,z,d;
int gcd(int a,int b)
{
    if (b==0) { x=1; y=0; return a; } else
    {
        int l=gcd(b,a%b);
        z=x; x=y;
        y=z-(a/b)*y;
        return l;
    }
}
int main() {
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d %d",&a,&n);
d=gcd(a,n);
while (x<0) x+=n;
printf("%d",x);
return 0;
}