function to find the primitive root of a number for positive integer n and given integer a that satisfies gcda n 1 the order of a modulo n is the smallest positive integer k that satisfies pow a k n 1 in other words ak 1 mod n order of certain number may or may not be exist if so return 1 find order for positive integer n and given integer a that satisfies gcda n 1 time complexity onlogn exception handeling 1 is the order of of 1 euler s totient function also known as phifunction n counts the number of integers between 1 and n inclusive which are coprime to n two numbers are coprime if their greatest common divisor gcd equals 1 code from algorithmsmathseulertotient py written by goswamirahul euler s totient function or phi function time complexity osqrtn result n for i in range2 intn 0 5 1 if n i 0 while n i 0 n i result result i if n 1 result result n return result def findprimitiverootn if n 1 exception handeling 0 is the only primitive root of 1 return 0 phi eulertotientn prootlist to have order a and n must be relative prime with each other for positive integer n and given integer a that satisfies gcd a n 1 the order of a modulo n is the smallest positive integer k that satisfies pow a k n 1 in other words a k 1 mod n order of certain number may or may not be exist if so return 1 find order for positive integer n and given integer a that satisfies gcd a n 1 time complexity o nlog n exception handeling 1 is the order of of 1 euler s totient function also known as phi function ϕ n counts the number of integers between 1 and n inclusive which are coprime to n two numbers are coprime if their greatest common divisor gcd equals 1 code from algorithms maths euler_totient py written by goswami rahul euler s totient function or phi function time complexity o sqrt n for positive integer n and given integer a that satisfies gcd a n 1 a is the primitive root of n if a s order k for n satisfies k ϕ n primitive roots of certain number may or may not exist if so return empty list exception handeling 0 is the only primitive root of 1 it will return every primitive roots of n to have order a and n must be relative prime with each other
import math


def find_order(a, n):
    
    if (a == 1) & (n == 1):
        
        return 1
    if math.gcd(a, n) != 1:
        print ("a and n should be relative prime!")
        return -1
    for i in range(1, n):
        if pow(a, i) % n == 1:
            return i
    return -1


def euler_totient(n):
    
    result = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result


def find_primitive_root(n):
    if n == 1:
        
        return [0]
    phi = euler_totient(n)
    p_root_list = []
    
    for i in range (1, n):
        
        if math.gcd(i, n) == 1:
            order = find_order(i, n)
            if order == phi:
                p_root_list.append(i)
    return p_root_list