// Invers modular.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#pragma warning(disable:4996)
using namespace std;

FILE* fin, * fout;

int A, N, X, Y, d;

void Euclid(int a, int b, int& d, int& X, int& Y)
{
	if (b == 0)
	{
		d = a;
		X = 1, Y = 1;
	}
	else
	{
		int X0, Y0;
		Euclid(b, a % b, d, X0, Y0);
		X = Y0;
		Y = X0 - a / b * Y0;
	}
}

static inline void Read()
{
	fin = fopen("inversmodular.in", "r");
	fout = fopen("inversmodular.out", "w");
	fscanf(fin, "%d %d", &A, &N);
}

static inline void Solve()
{
	Euclid(A, N, d, X, Y);
	while (X < 0)
		X += N;
	fprintf(fout, "%d", X);
}

int main()
{
	Read();
	Solve();
	return 0;
}