#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long

ifstream fin ( "inversmodular.in" );
ofstream fout ( "inversmodular.out" );

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

signed main() {
  int n, k, inv, idk;
  fin >> n >> k;
  inv = 0;
  invmod( inv, idk, n, k );
  if ( inv < 0 )
    inv += n;
  fout << inv % n;
  return 0;
}