#include<stdio.h>
int A,N;
int exp_log(int x)
{
	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;
}
int indicator(int x)
{
	float ind = x;
	for(int i = 2 ; x!=1 ;i++)
		if(x%i==0)
		{
			for(;x%i==0;x/=i);
			ind*=(1 - (1.0/i));
		}
	return (int)ind;
}
void rezolva()
{
	printf("%d",exp_log(indicator(N)-1));
}
void citire()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&A,&N);
}
int main()
{
	citire();
	rezolva();
	return 0;
}