#include <bits/stdc++.h>
using namespace std;
long long a, b, phii[1000000], j, n, phi_n, divv[1000000], i, x;
const long long E9 = 1e9;
bool pr(long long n) {
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return true;
  return false;
}
void phactor(long long n) {
  j = -1;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      j++;
      divv[j] = i;
    }
  }
  for (i = j; i >= 0; i--)
    if (divv[i] * divv[i] != n) {
      j++;
      divv[j] = n / divv[i];
    }
}
long long phi(long long n) {
  long long ans = n;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      ans -= ans / i;
    }
  if (n > 1) ans -= ans / n;
  return ans;
}
long long multiply(long long a, long long b) {
  long long ans = 0;
  long long a1 = a / E9;
  long long a2 = a % E9;
  int x = a2, dl = 0, dl2 = 0;
  while (x != 0) {
    dl++;
    x /= 10;
  }
  long long b1 = b / E9;
  long long b2 = b % E9;
  x = b2;
  while (x > 0) {
    dl2++;
    x /= 10;
  }
  long long ans1 = (a1 * b1);
  if (ans1 >= 1e15) ans1 %= n;
  for (int i = 0; i < dl + dl2; i++) {
    ans1 *= 10;
    if (ans1 >= 1e15) ans1 %= n;
  }
  long long ans2 = (b1 * a2) % n;
  long long ans3 = (b2 * a1) % n;
  for (int i = 0; i < dl; i++) {
    ans2 *= 10;
    if (ans2 >= 1e15) ans2 %= n;
  }
  for (int i = 0; i < dl2; i++) {
    ans3 *= 10;
    if (ans3 >= 1e15) ans3 %= n;
  }
  long long ans4 = (b2 * a2);
  if (ans1 >= n) ans1 %= n;
  if (ans2 >= n) ans2 %= n;
  if (ans3 >= n) ans3 %= n;
  if (ans4 >= n) ans4 %= n;
  long long res = ans1 + ans2 + ans3 + ans4;
  if (res >= n) res %= n;
  return res;
}
long long pow_mod(long long a, long long power) {
  if (power == 0) return 1ll;
  if (power & 1) {
    long long m = pow_mod(a, (power >> 1));
    m = multiply(m, m);
    return multiply(m, a);
  } else {
    long long m = pow_mod(a, (power >> 1));
    return multiply(m, m);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a;
  phactor(phi(n));
  for (i = 0; i <= j; i++) {
    if (pow_mod(a, divv[i]) == 1) {
      cout << (n - 1) / (divv[i]) + ((n - 1) % divv[i] != 0) + 1;
      return 0;
    }
  }
  return 0;
}
