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

void euclid_e(int a,int b,int& x,int& y,int& d){
 if(b==0) {
  d=a;
  x=1;
  y=0;
  return;
 }
 int xx,yy,q=a/b;
 euclid_e(b,a%b,xx,yy,d);
 x=yy;
 y=xx-yy*q;
}

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

  euclid_e(a,n,x,y,d);
  x%=n;
  if(x<0){
    x+=n;
  }

  fprintf(fout,"%d",x);

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