#include<stdio.h>
#include<math.h>
long long int A,N;
long long int exp_log(long long int x)
{
	long long int numar = 1,putere = x;
	while(putere!=0)
	{
		if(putere%2)
			numar = (1LL * A * numar) %N,putere--;
		A = (1LL * A * A) %N,putere/=2;
	}
	return numar;
}
long long int indicator(long long int x)
{
	double ind = x;
	long long int aux = sqrt(x*1.0);
	for(long long int i = 2 ; x!=1 && i<= aux+1; i++)
		if(x%i==0)
		{
			for(;x%i==0;x/=i);
			ind*=(1 - (1.0/i));
		}
	if(x!=1)
		ind*=(1 - (1.0/x));
	return (long long int)ind;
}
void rezolva()
{
	printf("%lld",exp_log(indicator(N)-1));
}
void citire()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&A,&N);
}
int main()
{
	citire();
	rezolva();
	return 0;
}