6
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Do you know what the number of generators are, given $n$? $\endgroup$ – Tobias Kildetoft Jan 29 '18 at 10:29
  • $\begingroup$ en.wikipedia.org/wiki/… You're welcome. :) $\endgroup$ – freakish Jan 29 '18 at 10:35
  • $\begingroup$ @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. $\endgroup$ – SlowerPhoton Jan 29 '18 at 10:42
  • 1
    $\begingroup$ @SlowerPhoton Yes, they do. An element generates $\mathbb{Z}_n$ if and only if it is relatively prime to $n$. $\endgroup$ – freakish Jan 29 '18 at 10:43
  • $\begingroup$ @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. $\endgroup$ – freakish Jan 29 '18 at 16:00
16
$\begingroup$

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)$
$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Jeppe Stig Nielsen Jan 29 '18 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.