#include <stdio.h>
#include <stdlib.h>

int exp_log_rec(int x, int n)
{
  if(n < 0)
    {
      return exp_log_rec(1.0 / x, -n);
    }
 
  if(n == 0)
    {
      return 1;
    }
 
  if(n % 2 == 0)
    {
      return exp_log_rec(x*x, n/2);
    }
 
  else // if(n % 2 == 1)
    {
      return x * exp_log_rec(x*x, n/2);
    }
}

int phi(int n)
{
  int result = n;
 
  for (int i = 2; i * i <= n; i++)
    {
      if (n % i == 0)
	{
	  while (n % i == 0)
	    {
	      n /= i;
	    }
	  result -= result / i;
	}
    }
  
  if (n > 1)
    {
      result -= result / n;
    }

  return result;
}

int main ()
{
  int a;

  int n;

  FILE *file_in = NULL;
  FILE * file_out = NULL;

  if((file_in = fopen("inversmodular.in","r")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE CITIRE !");
      exit(-1);
    }

  if((file_out = fopen("inversmodular.out","w")) == NULL)
    {
      perror("EROARE LA DESCHIDEREA FISIERULUI DE SCRIERE !");
      exit(-1);
    }

  fscanf(file_in,"%d",&a);

  fscanf(file_in,"%d",&n);
  
  int functiaPhi = 0;
  
  functiaPhi = phi(n);

  int a_la_phi_1 = 0;

  a_la_phi_1 = exp_log_rec(a,functiaPhi-1);

  fprintf(file_out,"%d",a_la_phi_1%n);
  
  fclose(file_in);
  
  fclose(file_out);
  
  return 0;
}