# Arup Guha
# Checks if a base is a primitive root a prime or not.
# 10/24/2022

# Returns each unique prime divisor of n
def getPrimeDiv(n):

    # Store all unique prime divisors here.
    res = []
    div = 2

    # Do trial division until the square root.
    while div*div <= n:

        # Divide out as many copies of div as possible.
        flag = False
        while n%div == 0:
            n //= div
            flag = True

        # We found one, so a new prime divisor.
        if flag:
            res.append(div)

        # Go to the next number.
        div += 1

    # See if anything is leftover.
    if n > 1:
        res.append(n)

    # We got them all.
    return res


# Runs the main program.
def main():

    # Get the prime and the base to test.
    p = int(input("Enter your prime.\n"))
    b = int(input("Enter your base to check as a primitive root.\n"))

    # Get all prime divisors of p-1.
    primediv = getPrimeDiv(p-1)

    # Here are all of our candidates. If any of these are 1, it's not
    # primitive.
    flag = True
    for x in primediv:
        if pow(b, (p-1)//x, p) == 1:
            flag = False
            break

    # Ta da!
    if flag:
        print(b,"is a primitive root mod",p)
    else:
        print(b,"is NOT a primitive root mod",p)

main()