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 