#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// Luy thua nhi phan
ll powerMod(ll a, ll b, ll p) {
    ll res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % p;
        a = (__int128)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ll a, p;
    cin >> a >> p;

    ll phi = p - 1;  // phi(p) = p - 1 vi p la so nguyen to
    ll ans = phi;     // Bac lon nhat co the la p-1

    // Duyet cac uoc cua phi(p)
    for (ll d = 1; d * d <= phi; d++) {
        if (phi % d == 0) {
            // Kiem tra uoc d
            if (powerMod(a, d, p) == 1) {
                ans = min(ans, d);
            }
            // Kiem tra uoc phi/d
            ll e = phi / d;
            if (powerMod(a, e, p) == 1) {
                ans = min(ans, e);
            }
        }
    }

    cout << ans << endl;
    return 0;
}