#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
const int MN=1e6+5;
const ll INF=1e15;
ll tot,head[MN],k,m,dis[MN];
bool vis[MN];
struct edge{ll to,nxt,w;}e[MN<<2];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void add(ll u, ll v, ll w){e[++tot].nxt=head[u];head[u]=tot;e[tot].to=v;e[tot].w=w;}
void dijkstra(ll x){
    priority_queue<pll,vector<pll>,greater<pll> > q;
    for(int i=0; i<k; i++) dis[i]=INF;
    dis[x]=0;q.push({0,x});
    while(!q.empty()){
        ll u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u]; i; i=e[i].nxt){
            ll v=e[i].to,w=e[i].w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main(){
    k=read();m=read();
    for(int i=1; i<k; i++){
        add(i,(i+1)%k,1);
        add(i,(i*m)%k,0);
    }
    dijkstra(1);
    write(dis[0]+1);
    return 0;
}