#include <iostream>
#include <fstream>

std::ifstream f ("inversmodular.in");
std::ofstream g ("inversmodular.out");

using namespace std;

int gcd(int a, int c) {
    int b;
    int r;

    g << a << ' ' << c << ' ';

    if (c == 0) {
        return a;
    }
    else if (c == 1) {
        return c;
    }

    b = a/c;
    r = a%c;

    g << r << '\n';

    gcd(c, r);
}

int main()
{
    int n, m;
    f >> n >> m;
    cout << gcd(n, m);
    return 0;
}