Finding primitive roots modulo n code

Question

I'm trying to translate some code into another language but struggling to understand the math behind it.

The code is from this answer and is as follows:

from math import gcd as bltin_gcd

def primRoots(modulo):
    required_set = {num for num in range(1, modulo) if bltin_gcd(num, modulo) }
    return [g for g in range(1, modulo) if required_set == {pow(g, powers, modulo)
            for powers in range(1, modulo)}]

I've been looking up lots of different ways that someone can determine primitive roots but don't totally understand what is going on here - both mathematically and programmatically.

Some insight is appreciated!

Answer 1

It's just checking if there exists a bijective map $$\{g^y:\gcd(g,n)=1, 1\leq y\leq \phi(n) \}\leftrightarrow\{x:1\leq x< n \gcd(x,n)=1\}$$

It really could be quicker. We know additive inverses produce additive inverses when raised to odd powers, so if maximum order is $2\bmod 4$ then $a,-a$ can't both be primitive roots (as $-1$ will be at an odd position in one creating $1$ in the other sequence). Meanwhile, we know $a,a^{-1}$ (multiplicative inverses) have same order , so if one of them is primitive then so is the other ( e.g. $3,5\bmod 7$). Further, as pointed out in the comments, if $g$ is primitive so are $g^k$ where $k$ doesn't share a factor with the order.