#include <stdio.h>
#include <stdbool.h>

// Congruenta(teoria numerelor):
//   Fie n un numar natural pozitiv. Spunem ca doua numere a si b sunt congruente modulo n
//   daca (a - b) % n = 0 si notam: a ≡ b (mod n)
// 1. Aritmetica modulara, propietati:
//     a) (a + b) % c = (a % c + b % c) % c
//     b) (a * b) % c = ((a % c) * (b % c)) % c
//     c) (a - b) % c = (a % c - b % c) % c
//     d) (a / b) % c = ((a % c) * (b^-1 % c)) % c, unde b^-1 este invers modularul lui b si c.
//    Exemplu, daca a = 10^18 si b = 10^19 si c = 10^9 + 7 atunci
//        a + b ar depasi 2^64, astel putem folosi propietatea si sa gasim rezultatul dorit, adica
//        (a % c + b % c) % c
// 2. Invers modular:
//     Ce este: Sa presupunem ca trebuie sa rezolvam ecuatia A * B = 1, este simplu ca B = 1/A sau A^-1.
//       Acum sa presupunem ca trebuie sa rezolvam (A * B) % M = 1, aici B este invers modularul lui A modulo M 
//       si B este din intervalul [1, M - 1].
//       Un invers modular(B) exista daca si numai daca gcd(A, M) = 1, adica daca A si M sunt coprime/relativ prime intre ele.

bool get_invers_modular(int a, int m, int *inv);
int egcd(int a, int b, int *x, int *y);

int main()
{
	FILE *in = fopen("inversmodular.in", "r");
	FILE *out = fopen("inversmodular.out", "w");
	if(in != NULL && out != NULL)
	{
		int a, b;
		fscanf(in, "%d%*c%d", &a, &b);
		int v;
		get_invers_modular(a, b,  &v);
		if(v <= 0)
		{
			v = b + inv % b;
		}
		fprintf(out, "%d\n", v);

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

int egcd(int a, int b, int *x, int *y)
{
	if(a == 0)
	{
		*x = 0;
		*y = 1;
		return b;
	}
	else
	{
		int x1, y1;
		int d = egcd(b % a, a, &x1, &y1);
		*x = y1 - (b / a) * x1;
		*y = x1;
		return d;
	}
}

bool get_invers_modular(int a, int m, int *inv)
{
	// Pentru a calcula invers modularul lui a mod m, adica numarul b a.i (a * b) % m = 1
	// ne vom folosi de algoritmul lui Euclid extins.
	// NOTA: Exista un invers modular doar daca gcd(a, m) = 1
	int x, y;
	int d = egcd(a, m, &x, &y);
	if(d != 1)
	{
		printf("Nu este invers modular\n");
		return false;
	}
	else
	{
		// FORMULA: xg = (xg % m + m) % m;
		x = (x % m + m) % m;
		*inv = x;
	}
	return true;
}