Find a group G containing exactly 44 elements x s.t. x generates G

Question

I think the solution would be to check all $\mathbb{Z}_n$ and count all elements which are relatively prime to $n$. If there is 44 of them, I've found an example of such group. However this is a pretty long process. Can you think of a better solution? Or can I optimize this somehow?

Answer 1

So first of all note that $x\in\mathbb{Z}_n$ generates $\mathbb{Z}_n$ if and only if $\gcd(x,n)=1$.

So you are looking for a solution to the equation

$$\varphi(n)=44$$

were $\varphi$ is the Euler's totient function. You can simply just look up a solution. But let's try to reverse engineer it. The function has some nice properties, e.g.

$$\varphi(xy)=\varphi(x)\varphi(y)\text{ if }x,y\text{ are relatively prime}$$ $$\varphi(p)=p-1\text{ for prime }p$$

So let's try:

1. $45$ is not prime. Can't use the second property. Bad luck.
2. $44=2\cdot 22$
3. Both $3$ and $23$ are prime (and relatively prime)
4. $44=2\cdot 22=\varphi(3)\cdot\varphi(23)=\varphi(3\cdot 23)=\varphi(69)$