#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()
{	

    ifstream f("inversmodular.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 + b;
	    
        printf("%d", x);      
			   
	
       
       
   return 0;          
}