#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define inl long long
using namespace std;

inl Power(inl a,inl b,inl m){
  inl r;
  r=1;
  while(b>0){
    if(b%2==1){
      r*=a;
      r%=m;
      b--;
    }
    a*=a;
    a%=m;
    b/=2;
  }
  return r;
}

inl FormulaFi(inl n){
  inl ans,i;

  ans=n;
  for(i=2;i*i<=n;i++){
    if(n%i==0){
      while(n%i==0){
        n/=i;
      }
      ans=(ans/i)*(i-1);
    }
  }
  if(n!=1){
    ans=(ans/n)*(n-1);
  }
  return ans;
}

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

int main(){
  inl a,n,x,y;
  FILE *fin,*fout;
  fin=fopen("inversmodular.in","r");
  fout=fopen("inversmodular.out","w");
  fscanf(fin,"%lld%lld",&a,&n);

  //fprintf(fout,"%lld",Power(a,FormulaFi(n)-1,n));
  CMMDCExtins(a,n,x,y);
  while(x<0){
    x=n+x%n;
  }
  fprintf(fout,"%lld",x);

  fclose(fin);
  fclose(fout);
  return 0;
}