Primitive Roots
June 7, 2019
In modular arithmetic, a number g is a primitive root of n if, for every a coprime to n, there exists some k such that gk ≡ a (mod n). The concept of a primitive root was developed by Gauss and pops up from time to time in work on cryptography and number theory.
There is no formula for computing a primitive root, but they are common enough that it is easy to just randomly search for them; more commonly, people just start at 2 and work their way up. Once a primitive root has been found, the remaining primitive roots of n can be found by exponentiating mod n.
Your task is to write a program that computes the primitive roots of prime n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. The function factors can be e.g.: factors by trial division.
def totient(n, factors=factors): result = n for prime in set(factors(n)): result -= result // prime return result def prim_roots(n): """ find all primitive roots for any positive n find one root, then generate the other by exponentiation root g is found, if g is coprime to n and g^(phi/pi) != 1 for all prime factors pi in totient(n) """ if n == 1: # according to Wikipedia return [0] phi = totient(n) prs = set(factors(phi)) for g in range(1, n): if gcd(g, n) != 1: # g should be coprime with n continue if all(pow(g, phi // pi, n) != 1 for pi in prs): return sorted(pow(g, k, n) for k in range(1, n) if gcd(k, phi) == 1) return []