#include<cstdio>
    using namespace std;
    int A , N  ,x , y;

    void euclid(int a , int b , int &x , int&y);

    int main()
    {
        freopen("inversmodular.in" , "r" , stdin );
        scanf("%d%d" , &A , &N );
        euclid(N,A,x,y);
        while(y < 0)y+=N;
        freopen("inversmodular.out" , "w" , stdout );
        printf("%d" , y);
        return 0;
    }

    void euclid(int a , int b , int &x , int &y)
    {
        if(b == 0)
        {
            x = 1 , y = 0;
        }
        else{
            int x0,y0;
            euclid(b,a%b,x0,y0);
            y = x0-a/b*y0;
            x = y0;
        }
    }