---

# ---------- Факторизация n ----------
def prime_factors(n):
    factors = set()
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.add(d)
            n //= d
        d += 1
    if n > 1:
    return factors


# ---------- Быстрое возведение в степень ----------
def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result


# ---------- Простая проверка простоты (перебор до √n, шаг 2) ----------
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True


# ---------- ПРОВЕРКА: является ли g примитивным корнем по модулю p ----------
def is_primitive_root(g, p):
    # 1) p должно быть простым
    if not is_prime(p):
        return False, f"p = {p} не простое"

    # 2) g должно быть в диапазоне 1 < g < p
    if g <= 1 or g >= p:
        return False, f"g = {g} вне диапазона (1, {p})"

    # 3) p-1 факторизуем
    phi = p - 1
    factors = prime_factors(phi)

    # 4) для каждого простого делителя f числа p-1: g^((p-1)/f) mod p != 1
    for f in factors:
        val = mod_pow(g, phi // f, p)
        print(f"    g^((p-1)/{f}) mod p = {g}^{phi // f} mod {p} = {val}")
        if val == 1:
            return False, f"не примитивный: g^((p-1)/{f}) mod p == 1"

    return True, "примитивный корень"


# ---------- Ввод p и g с клавиатуры ----------
def main():
    print("=== Проверка примитивного корня ===")
    try:
        p = int(input("Введите простое число p: ").strip())
        g = int(input("Введите число g: ").strip())
    except ValueError:
        print("[!] Нужно вводить целые числа")
        return

    ok, msg = is_primitive_root(g, p)
    if ok:
        print(f"\n[+] g = {g} ЯВЛЯЕТСЯ примитивным корнем по модулю p = {p}")
    else:
        print(f"\n[-] g = {g} НЕ является примитивным корнем по модулю p = {p}")
        print(f"    Причина: {msg}")


if __name__ == "__main__":
    main()