Primitive root for a prime P is number g in [1,P-1] such that g^x mod P gives all [1,P-1], with x in [1,P-2]

Need to find: 1. Smallest primitive root of p 2. Total primitive roots of p

Solution logic: 1. determine all the prime factor of phi = p - 1 as p1, p2, ... pk 2. For each candidate g for each prime factor pj if g^(phi/pj) mod != 1

    if above condition is met for all pj, it is a root

3. Once one primitive root is found, others can be obtained as g^m where gcd(m, phi) == 1 i.e. they should be coprime

'''

def gcd_AB(a: int, b:int) -> int:
    if b > a:
        a, b = b, a
    if a%b == 0:
        return b
        
    return gcd_AB(b, a%b)

def isPrime(n: int) -> bool:
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 ==0 or n% 3 == 0:
        return False
    
    i = 5
    while i*i <= n:
        if n % i == 0 or n % (i+2) == 0:
            return False
        i = i + 6

    return True

def get_prime_factors(n: int) -> set[int]:
    """Fast prime factorization using trial division up to sqrt(n)."""
    factors = set()

    while n % 2 == 0:
        factors.add(2)
        n //= 2

    f = 3
    while f * f <= n:
        while n % f == 0:
            factors.add(f)
            n //= f
        f += 2

    if n > 1:
        factors.add(n)

    return factors

def primitive_root_check(g: int, phi_factors: list[int], p: int) -> bool:
    """Check if g is a primitive root modulo p."""
    return all(pow(g, (p - 1) // q, p) != 1 for q in phi_factors)

def primitive_roots(p: int) -> set[int]:
    """Find all primitive roots modulo p."""
    phi_factors = list(get_prime_factors(p - 1))

    # Find smallest primitive root
    for g in range(2, p):
        if primitive_root_check(g, phi_factors, p):
            primitive = g
            break

    # Generate all primitive roots from the smallest one
    roots = {pow(primitive, k, p) for k in range(1, p) if gcd_AB(k, p - 1) == 1}
    return roots

if __name__ == '__main__':
    p = int(input().strip())
    primitive_roots_list = primitive_roots(p)
    print(primitive_roots_list)

print (min(primitive_roots_list), len(primitive_roots_list))

I highly recommend this insightful and thought-provoking piece to anyone seeking knowledge and a deeper understanding of the subject.

This solution with python , but has some test faild because of Time limit exceeded .

import math

import os

import random

import re

import sys

def power(x, y, p):

result = 1

x = x % p

while y > 0:

if y & 1:

result = (result * x) % p

y = y >> 1

x = (x * x) % p

return result

def is_primitive_root(g, p, factors):

for factor in factors:

if power(g, (p - 1) // factor, p) == 1:

return False

return True

def find_primitive_roots(p):

primitive_roots = []

factors = set()

# Find prime factors of p-1

for i in range(2, int(math.sqrt(p-1)) + 1):

if (p - 1) % i == 0:

factors.add(i)

factors.add((p - 1) // i)

for g in range(2, p):

if is_primitive_root(g, p, factors):

primitive_roots.append(g)

return primitive_roots

def smallest_primitive_root(p):

primitive_roots = find_primitive_roots(p)

return min(primitive_roots)

if name == 'main':

p = int(input().strip())

smallest_root = smallest_primitive_root(p)

total_roots = len(find_primitive_roots(p))

print(smallest_root, total_roots)

This solution with python , but has some test faild because of Time limit exceeded .

import math import os import random import re import sys

def power(x, y, p): result = 1 x = x % p while y > 0: if y & 1: result = (result * x) % p y = y >> 1 x = (x * x) % p return result

def is_primitive_root(g, p, factors): for factor in factors: if power(g, (p - 1) // factor, p) == 1: return False return True

def find_primitive_roots(p): primitive_roots = [] factors = set() # Find prime factors of p-1 for i in range(2, int(math.sqrt(p-1)) + 1): if (p - 1) % i == 0: factors.add(i) factors.add((p - 1) // i)

for g in range(2, p):
    if is_primitive_root(g, p, factors):
        primitive_roots.append(g)
return primitive_roots

def smallest_primitive_root(p): primitive_roots = find_primitive_roots(p) return min(primitive_roots)

if name == 'main': p = int(input().strip())

smallest_root = smallest_primitive_root(p)
total_roots = len(find_primitive_roots(p))

print(smallest_root, total_roots)

To find the smallest primitive root and the total number of primitive roots for a given prime number, we can use mathematical concepts. Primitive roots are fascinating mathematical objects, and they play a crucial role in number theory