#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
int c,d,n,e;


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

int main()
{	
	int i;
    ifstream f("euclid3.in");  
	freopen("inversmodular.out","w",stdout);
	
	
		int a, b, c, d, x, y;
		f>>a>>b;
       
		c = 1;
		euclid(a,b,d,x,y);
		
	    while ( x < 0)  x = x + a;
	    
        printf("%d ", x);      
			   
	
       
       
   return 0;          
}