#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;
const int INF32 = 1e9;

int N, M, f[MAX_N];
priority_queue<pair<int,int>> pq;

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; i ++) {
        f[i] = INF32;
    }
    for (int i = 1; i < M; i ++) {
        int j = i % N;
        if (f[j] > i) {
            f[j] = i;
            pq.push(make_pair(-f[j], j));
        }
    }
    while (pq.size()) {
        auto tmp = pq.top();
        pq.pop();
        int x = tmp.second;
        if (tmp.first != -f[x]) continue;
        for (int i = 0; i < M; i ++) {
            int y = (x * M + i) % N;
            if (f[y] > f[x] + i) {
                f[y] = f[x] + i;
                pq.push(make_pair(-f[y], y));
            }
        }
    }
    printf("%d\n", f[0]);
    return 0;
}