1. ## Cannot find the contradiction

Hello all. I have something in which there must be a contradiction but I cannot find it.

So let $\displaystyle \phi$ be the usual Euler phi/totient function, and let $\displaystyle G$ be a finite group. Then we have

(1) $\displaystyle \phi_G(d) = \phi(d) \cdot q(d)$
where $\displaystyle q(d)$ = the number of cyclic subgroups of order $\displaystyle d$ and $\displaystyle \phi_G(d)$ = the number of elements of order $\displaystyle d$ in $\displaystyle G$.

Then we also have the theorem
(2) $\displaystyle \displaystyle\sum_{d | n} \phi(d) = n.$
But I have a theorem in my notes

which states $\displaystyle \displaystyle\sum_{d | |G|} \phi_G (d) = |G|$. But by (1), this is equivalent to the statement $\displaystyle \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|$.

But doesn't this contradict (2) ? Unless $\displaystyle q(d) = 1 \text{ whenever } \phi(d) \not= 0$ which cannot be true otherwise there would be no point looking at $\displaystyle \phi_G(d)$. Can anyone help?

2. Actually, it turns out that $\displaystyle q(d)$ may be 0 for some $\displaystyle d| |G|$.

For example: a finite group $\displaystyle G$ is not cyclic iff $\displaystyle q(|G|) = 0$.

3. Originally Posted by slevvio
Hello all. I have something in which there must be a contradiction but I cannot find it.

So let $\displaystyle \phi$ be the usual Euler phi/totient function, and let $\displaystyle G$ be a finite group. Then we have

(1) $\displaystyle \phi_G(d) = \phi(d) \cdot q(d)$
where $\displaystyle q(d)$ = the number of cyclic subgroups of order $\displaystyle d$ and $\displaystyle \phi_G(d)$ = the number of elements of order $\displaystyle d$ in $\displaystyle G$.

Then we also have the theorem
(2) $\displaystyle \displaystyle\sum_{d | n} \phi(d) = n.$
But I have a theorem in my notes

which states $\displaystyle \displaystyle\sum_{d | |G|} \phi_G (d) = |G|$. But by (1), this is equivalent to the statement $\displaystyle \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|$.

But doesn't this contradict (2) ? Unless $\displaystyle q(d) = 1 \text{ whenever } \phi(d) \not= 0$ which cannot be true otherwise there would be no point looking at $\displaystyle \phi_G(d)$. Can anyone help?
It's possible $\displaystyle q(d)=0$, in fact it happens often.

4. Originally Posted by slevvio
Hello all. I have something in which there must be a contradiction but I cannot find it.

So let $\displaystyle \phi$ be the usual Euler phi/totient function, and let $\displaystyle G$ be a finite group. Then we have

(1) $\displaystyle \phi_G(d) = \phi(d) \cdot q(d)$
where $\displaystyle q(d)$ = the number of cyclic subgroups of order $\displaystyle d$ and $\displaystyle \phi_G(d)$ = the number of elements of order $\displaystyle d$ in $\displaystyle G$.

Then we also have the theorem
(2) $\displaystyle \displaystyle\sum_{d | n} \phi(d) = n.$
But I have a theorem in my notes

which states $\displaystyle \displaystyle\sum_{d | |G|} \phi_G (d) = |G|$. But by (1), this is equivalent to the statement $\displaystyle \displaystyle\sum_{d | |G|} \phi(d) q(d) = |G|$.

But doesn't this contradict (2) ? Unless $\displaystyle q(d) = 1 \text{ whenever } \phi(d) \not= 0$ which cannot be true otherwise there would be no point looking at $\displaystyle \phi_G(d)$. Can anyone help?
I don't particularly understand you're confusion, I don't see an immediate contradiction. One way that someone could define this is to define the relation $\displaystyle \overset{\text{gen}}{\sim}$ on $\displaystyle G$ by $\displaystyle g\overset{\text{gen}}{\sim}h$ if and only if $\displaystyle \langle g\rangle=\langle h\rangle$. If one then calls the equivalence classes of this (clearly equivalence) relation $\displaystyle \text{gen}(g)$ then one has that $\displaystyle \displaystyle G=\biguplus_{g\in\Gamma}\text{gen}(g)$ where $\displaystyle \Gamma$ is a set which contains one representative from each equivalence class. It follows then that $\displaystyle \displaystyle |G|=\sum_{g\in\Gamma}\#\left(\text{gen}(g)\right)$ but it's not hard to prove that $\displaystyle \#\left(\text{gen}(g)\right)=\varphi\left(|g|\righ t)q(|g|)$ (using your notation) and thus, we may conclude that $\displaystyle \displaystyle |G|=\sum_{g\in\Gamma}\varphi(|g|)q(|g|)$ but it shouldn't be hard to convince yourself that this can be written (recalling Lagrange's theorem and the fact that even if the group does not contain any cyclic subgroups of order $\displaystyle d\mid n$ then one may add the term since it's zero) as $\displaystyle \displaystyle |G|=\sum_{d\mid |G|}\varphi(d)q(d)$. So, this in particular proves that $\displaystyle \displaystyle \sum_{d\mid n}\varphi(g)=n$ by considering that $\displaystyle \mathbb{Z}/n\mathbb{Z}$ has exactly one subgroup (and of course this implies one cyclic subgroup) for each divisor of $\displaystyle n$. How does using these facts contradict anything?

5. I just got confused since q(d) may = 0 while $\displaystyle \phi(d)$ doesn't