#include <iostream>
#include <cstdio>
using namespace std;
void invm(int a,int b,long long &x , long long & y){
 if(!b){
   x=1;
   y=0;
   return;
 }
 else{
  long long aux;
  invm(b,a%b,x,y);
  aux = x;
  x=y;
  y= aux - y*(a/b);
 }
}
int main(){
    long long x,y;
    int a,n;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
    x=0;
    invm(a,n,x,y);
    if(x <= 0)
     x = x%n+n;

    printf("%lld\n",x);
    return 0;
}