How to get the actual values from Euler's Phi function

Question

I would like to get the list of actual values from Euler's Phi function. For example:

$$\phi(12) = |1,5,7,11| = 4 $$ and I would like to get the actual list $$[1,5,7,11]$$

Of course the naive way is to calculate all the gcd values, but I'm looking to something faster.

I tried using the following property:

$$p \in PRIMES, k \in \mathbb{N} => \phi(p^k) = p^{k-1}(p-1)$$

$$\phi(n) = \phi(\prod{p_1^{k_1}\cdot\cdot\cdot p_m^{k_m}}) = \phi(p_1^{k_1})...\phi(p_m^{k_m}) = p_1^{k_1-1}(p_1-1)\cdot\cdot\cdot p_m^{k_m-1}(p_m-1) $$

but even in the simple case of $$\phi(12)$$ it is not clear to me how to get the list.

Is there such an algorithm?

Answer 1

Well, a number smaller than $n$ is relatively prime to $n$ if and only if it is not divisible by any of $n$'s prime factors. That gives you a simple algorithm to find the numbers relatively prime to $n$.
1) Find all primes dividing $n$.
2) Go through all numbers $1,2,3,...,(n-1)$ and see if they are divisible by any of the primes which divide $n$.

In your example you have $1,5,7,11$, these are just the numbers smaller than $12$ which are not divisible by $2$ and $3$.

Answer 2

Using the *Chinese Reaminder theorem`, you come down todetermine the units $\mathbf Z/p^r\mathbf Z$ for prime $p$.

If $p=2$, it's very simple: all odd numbers in $[1 , p^r-1]$ are units.

If $p$ is an odd prime, the group of units is cyclic. Hence you can test all integers $a$, starting with $2$, computing their powers, until you find one with order $p^{r-1}(p-1)$. This should be faster than computing all g.c.d.s, all the more so as often a generator is obtained for a small value of $a$.