#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include<cstdlib>
using namespace std;
	
#define MAXN 101

//#define MOD 1999999973

#define INF 1<<30

int v[MAXN];

void euclidExtins (int a, int b, int long long &x, int long long &y)
{
	if ( b == 0 )
	{
		x = 1; 
		y = 0;
	}
	else
	{
		euclidExtins (b, a % b, x, y);
		int long long aux = x;
		x = y;
		y = aux - y * (a / b);
	}
}

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

	long long int A, N;
	fscanf(f, "%lld %lld", &A, &N); 
	
	long long int inversModular = 0, y;

	euclidExtins(A, N, inversModular, y);

	if (inversModular <= 0)
	{
		inversModular = N + inversModular % N;
	}

	fprintf(g, "%d", inversModular);

	fclose(f); fclose(g);
	return 0;
}