#include <stdio.h>
#include <stdlib.h>

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

int main(){
	int a,n,x,y,d;
	FILE *f,*g;
	if((f=fopen("inversmodular.in","r"))==NULL){
		printf("eroare deschidere fisier\n");
		exit(1);
	}
	if((g=fopen("inversmodular.out","w"))==NULL){
		printf("eroare deschidere fisier\n");
		exit(1);
	}
	fscanf(f,"%d",&a);
	fscanf(f,"%d",&n);
	d=euclid(a,n,&x,&y);
	if(x<=0)
		x=n+x%n;
	fprintf(g,"%d",x);
	fclose(f);
	fclose(g);
	return 0;
}