#include <bits/stdc++.h>
#define int long long
int a,n;
void cmmdc(int a,int b,int *x,int *y)
{
  int x0,y0;
  if (b==0)
    *x=1,*y=0;
  else
  {
    cmmdc(b,a%b,&x0,&y0);
    *x = y0;
    *y = x0 - (a / b) * y0;
  }
}
int32_t main()
{
  int x,y;
  freopen("inversmodular.in","r",stdin);
  freopen("inversmodular.out","w",stdout);
  scanf("%d %d",&a,&n);
  cmmdc(a,n,&x,&y);
  printf("%d",((x%n)+n)%n);
  return 0;
}