#include "algorithm"
#include "array"
#include "cmath"
#include "complex"
#include "cstdio"
#include "deque"
#include "initializer_list"
#include "map"
#include "numeric"
#include "queue"
#include "regex"
#include "set"
#include "stack"
#include "string"
#include "unordered_map"
#include "vector"
#define FOR(i, n) for ((i) = 0; (i) < (n); ++(i))
#define in_int(x) scanf(" %d/n", &(x));
#define in_str(x) scanf(" %[a-zA-Z (+-0-9_) #.]/n", (x));
#define ch(x) printf("debag %d\n", (x))

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int dx_ar[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy_ar[] = {1, 0, -1, 1, -1, 1, 0, -1};

template <typename type> void print_array_horizon(type d1_arr);
template <typename type> void print_2darray(type d2_arr);
std::vector<std::vector<int>> padding(std::vector<std::vector<int>> arr,
                                      int pad);
inline std::vector<int> str_int_split(char *s);
inline std::vector<std::vector<int>> in_d2_arr(int N, int size = 1000);
inline std::vector<int> in_d1_arr(int size = 1000);
inline double d2_distance(int x1, int y1, int x2, int y2);
inline int d2_manhattan(int x1, int y1, int x2, int y2);
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long q = a / b;
  long long g = ext_gcd(b, a - q * b, x, y);
  long long z = x - q * y;
  x = y;
  y = z;
  return g;
}

int main() {
  long long a, b, x, y;
  long long g;
  std::vector<int> v;
  v = in_d1_arr();
  a = v[0];
  b = v[1];
  g = ext_gcd(a, b, x, y);
  printf("%lld\n", g);
}

template <typename type> void print_array_horizon(type d1_arr) {
  int i;
  FOR(i, d1_arr.size() - 1) { printf("%d ", d1_arr[i]); }
  printf("%d\n", d1_arr.back());
  fflush(stdout);
}

template <typename type> void print_2darray(type d2_arr) {
  int i, j;
  FOR(i, d2_arr.size()) {
    FOR(j, d2_arr[i].size() - 1) { printf("%d ", d2_arr[i][j]); }
    printf("%d\n", d2_arr[i].back());
    fflush(stdout);
  }
}

std::vector<std::vector<int>> padding(std::vector<std::vector<int>> arr,
                                      int pad) {
  std::vector<std::vector<int>> arr_c = arr;
  int height = arr_c.size();
  int width = arr_c[0].size();
  std::vector<int> v;
  v.resize(width);
  fill(v.begin(), v.end(), pad);
  arr_c.insert(arr_c.begin(), v);
  arr_c.push_back(v);
  int i;
  FOR(i, height + 2) {
    arr_c[i].insert(arr_c[i].begin(), pad);
    arr_c[i].resize(width + 2);
  }
  arr_c.shrink_to_fit();
  return arr_c;
}

inline std::vector<int> str_int_split(char *s) {
  char *tok = strtok(s, " ");
  std::vector<int> v;
  while (tok != NULL) {
    v.push_back(atoi(tok));
    tok = strtok(NULL, " "); /* 2回目以降 */
  }
  return v;
}

inline std::vector<std::vector<int>> in_d2_arr(int N, int size) {
  int i;
  std::vector<std::vector<int>> v;
  FOR(i, N) {
    char *lines;
    lines = new char[size];
    in_str(lines);
    v.push_back(str_int_split(lines));
    delete[] lines;
  }
  return v;
}

inline std::vector<int> in_d1_arr(int size) {
  std::vector<int> v;
  char *lines;
  lines = new char[size];
  in_str(lines);
  v = str_int_split(lines);
  delete[] lines;
  return v;
}

inline double d2_distance(int x1, int y1, int x2, int y2) {
  return sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2));
}

inline int d2_manhattan(int x1, int y1, int x2, int y2) {
  return (abs(x2 - x1) + abs(y2 - y1));
}



Measured memory_bytes: 2824