#include <stdio.h>

bool Prost(int k)
{
	for (int i=2; i<= k/2; ++i)
		if (k%i == 0) return false;

	return true;
}

int Inverz(int p, int k)
{
	if (k==1)
		return 1;
	else
		return ((p/k + 1)*Inverz(p, k - p%k) % p);
}

int main()
{
	int p, k;
	bool los_unos;

	do {
		printf("Unesi stepen polja 'p' i broj 0<k<p-1\n");
		los_unos = false;

		if (scanf("%d %d", &p, &k) != 2) {
			printf("Greska pri unosu! Probajte ponovo...\n");
			los_unos = true;
			_flushall();
			continue;
		}

		if (!Prost(p) || p<=1) {
			printf("Uneti broj p = %d nije prost! Probajte ponovo...\n", p);
			los_unos = true;
		}
		if ((k<=0)||(k>=p)) {
			printf("Uneti broj k = %d ne zadovoljava trazene uslove!. Probajte ponovo...\n", k);
			los_unos = true;
		}
	}
	while (los_unos);

	printf("Inverz broja %d u polju Z%d jednak je %d\n\n", k, p, Inverz(p, k));
	return 0;
}