// Invers modular.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("inversmodular.in", "r");
FILE *g=fopen("inversmodular.out", "w");


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


int main()
{
	long long a, n;
	long long inv=0, ins;

	fscanf(f, "%lld%lld", &a, &n);

	long long cmmdc=euclid(a, n, inv, ins);
	
	if (inv<=0)
		inv=n+inv%n;

	fprintf(g, "%lld", inv);

	return 0;
}