#include <stdio.h>

int ee(int a,int b,int &x,int &y)
{
    if (b == 0)    
    {
       x = 1;
       y = 0;
       return a;      
    }
    int d,x0,y0;
    d = ee(b,a%b,x0,y0);
    x = y0;
    y = x0 - (a/b)*y0;
    return d;
}

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    
    int a,n,sol,x;
    
    scanf("%d%d%d", &a,&n);
    
    ee(a,n,sol,x);
    
    printf("%d\n", sol);
        
    return 0;    
}