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

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?

• Do you know what the number of generators are, given $n$? – Tobias Kildetoft Jan 29 '18 at 10:29
• en.wikipedia.org/wiki/… You're welcome. :) – freakish Jan 29 '18 at 10:35
• @freakish How can I use it to my advantage? Yes, I can find that $\mathbb{Z}^{*}_{69}$ contains 44 elements, but that doesn't imply all of them generate it. – SlowerPhoton Jan 29 '18 at 10:42
• @SlowerPhoton Yes, they do. An element generates $\mathbb{Z}_n$ if and only if it is relatively prime to $n$. – freakish Jan 29 '18 at 10:43
• @knbk First of all $\mathbb{Z}_{69}^*$ has $44$ elements. Secondly the question is not about $\mathbb{Z}_n^*$ but $\mathbb{Z}_n$. The set of generators of $\mathbb{Z}_n$ is equal to $\mathbb{Z}_n^*$. It just happens that $x\in\mathbb{Z}_n$ generates $\mathbb{Z}_n$ (as a group under addition) if and only if $x$ is invertible in $\mathbb{Z}_n$ as a ring. – freakish Jan 29 '18 at 16:00

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)$
• A further investigation along these lines can show that $\varphi^{-1}(\{ 44\}) = \{ 3\cdot 23, 4\cdot 23, 2\cdot 3\cdot 23 \} = \{ 69,92,138 \}$. So up to isomorphism, there are three solutions for $G$. – Jeppe Stig Nielsen Jan 29 '18 at 19:23