#include <bits/stdc++.h>
using namespace std;
long long p[1005], q[1005], n, X, ans;
int num, tot;
long long phi(long long x) {
  long long ret = x;
  for (int i = 1; i <= num; i++)
    if (!(x % p[i])) ret /= p[i], ret *= p[i] - 1;
  return ret;
}
long long q_mul(long long x, long long y, long long mod) {
  return ((x * y - (long long)(((long double)x * y + 0.5) / mod) * mod) % mod +
          mod) %
         mod;
}
long long q_pow(long long x, long long n, long long mod) {
  long long ret = 1;
  for (; n; n >>= 1, x = q_mul(x, x, mod))
    if (n & 1) ret = q_mul(ret, x, mod);
  return ret;
}
void work(long long g) {
  long long mod = n / g, ph = phi(mod), x = X % mod, K = ph;
  for (int i = 1; i <= tot; i++)
    while (K % q[i] == 0 && q_pow(x, K / q[i], mod) == 1) K /= q[i];
  ans += ph / K;
}
void get_pri(long long x) {
  q[++tot] = x + 1;
  for (int i = 2; i <= (x / i); i++)
    if (x % i == 0) {
      q[++tot] = i;
      while (x % i == 0) x /= i;
    }
  if (x != 1) q[++tot] = x;
}
void init() {
  long long x = n;
  for (int i = 2; i <= (x / i); i++)
    if (x % i == 0) {
      p[++num] = i;
      while (x % i == 0) x /= i;
    }
  if (x != 1) p[++num] = x;
  for (int i = 1; i <= num; i++) get_pri(p[i] - 1);
  sort(q + 1, q + tot + 1);
  tot = unique(q + 1, q + tot + 1) - q - 1;
}
int main() {
  scanf("%lld%lld", &n, &X);
  init();
  int i;
  for (i = 1; i < (n / i); i++)
    if (n % i == 0) work(i), work(n / i);
  if (1ll * i * i == n) work(i);
  printf("%lld\n", ans);
  return 0;
}
