#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 2e6 + 100;
namespace dijkstra{
    vector<pair<int, ll>> g[N];
    bool vis[N];
    ll dis[N];
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    ll Dij(int s, int t){
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        ll _unr = dis[0];
        dis[s] = 0;
        q.push(make_pair(dis[s], s));
        while(!q.empty()){
            int u = q.top().second;q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i = 0;i < (int)g[u].size();i++){
                int v = g[u][i].first, w = g[u][i].second;
                if(dis[u] + w < dis[v]){
                    dis[v] = dis[u] + w;
                    q.push(make_pair(dis[v], v));
                }
            }
        }
        return dis[t];
    }
}
using namespace dijkstra;
int n, m;
int main(){
    cin >> n >> m;
    for(int x = 1;x < n;x++){
        for(int r = 0;r < m;r++){
            int u = x, v = (x * m + r) % n;
            g[u].push_back({v, r});
        }
    }
    int s = n;
    for(int r = 1;r < m;r++) g[s].push_back({r, r});
    ll ans = Dij(s, 0);
    cout << ans << endl;
    return 0;
}