#include<bits/stdc++.h>
using namespace std;
int n, m, head[1000005], nxt[20000007], to[20000007], w[20000007], ccnt, d[1000005], b[1000005], s, t;
inline void add(int p, int q, int ww) {
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	head[p] = ccnt;
	w[ccnt] = ww;
}
struct node {
	int name, num;
	bool operator<(const node& op)const {
		return num > op.num;
	}
};
void dijkstra() {
	for (int i = 1; i <= n; i++) {
		d[i] = (1 << 31) - 1;
	}
	s = 0;
	d[s] = 0;
	priority_queue<node> q;
	q.push(node{s, 0});
	memset(b, false, sizeof(b));
	while (q.size()) {
		node u = q.top();
		q.pop();
		if (b[u.name]) continue;
		b[u.name] = true;
		for (int i = head[u.name]; i; i = nxt[i]) {
			if (b[to[i]] == false && w[i] + d[u.name] < d[to[i]]) {
				d[to[i]] = w[i] + d[u.name];
				q.push(node{to[i], d[to[i]]});
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) {
			add(i, ((i * m + j) % n) == 0 ? n : (i * m + j) % n, j);
		}
		if (i != 0) {
			add(i, ((i * m) % n) == 0 ? n : (i * m) % n, 0);
		}
	}
	dijkstra();
	cout << d[n];
	return 0;
}