# Thread: Again, phi euler function

1. ## Again, phi euler function

hi, can anybody prove that?:

Let $G$ finite set.

$A=\{c \in{G} : a^k=e\}$

Prove that $\phi(k)/|A|$

( $\phi$ is the euler function)

Thanks

2. Originally Posted by asub1
hi, can anybody prove that?:

Let $G$ finite set.

$A=\{c \in{G} : a^k=e\}$

Prove that $\phi(k)/|A|$

( $\phi$ is the euler function)

Thanks
This is not true, just take $G = \mathbb{Z}_3$ and $k=3000$.

Maybe you mean to say $A = \{ a\in G : |a| = k \}$ where $|a|$ is order of $a$?

3. Maybe you mean to say ...
Yes, im sorry.
And " $|A|$ " i mean to say #A (the cardinal).

Thanks

4. We will define a relation $\leftrightarrow$ on $A$.
For, $a,b\in A$ define $a\leftrightarrow b$ iff $b = a^j$ for some $j\in \mathbb{Z}$.

If $a$ has order $k$ then $a^j$ has order $k$ if and only if $(k,j)=1$.

We argue that $\leftrightarrow$ is an equivalence relation. First, it is reflexsive because $a = a^1$ and so $a\leftrightarrow a$. Second, it is symmetric because if $a \leftrightarrow b \implies b = a^j$. Now since $(k,j)=1$ it means there is $j_0$ so that $jj_0 \equiv 1 (\bmod k)$. Thus, $b^{j_0} = a^{jj_0} = a$. We see from here that $b \leftrightarrow a$. Third, it is transitive because if $a \leftrightarrow b$ and $b \leftrightarrow c$ it means $b = a^{j_0}$ and $c = b^{j_1}$. Thus, $c = a^{j_0j_1}$ and so $a \leftrightarrow c$.

For $a \in A$ define $[a] = \{ x\in A | x \leftrightarrow a\}$. Because $\leftrightarrow$ is an equivalence relation it means $S = \{ x : x = [a] \text{ for some }a\in A\}$ is a partition of $A$. Let $r$ be the number of such partitions, i.e. $r = |S|$. We will prove that $[a] = \{ a^j | 1\leq j\leq k , (k,j)=1\}$. We say above, second paragraph that if $a\in A$ for $a^j$ to be in $A$ i.e. for $a^j$ to have order $k$ it is necessary and sufficient for $(k,j)=1$. Therefore, $[a]$ consists of elements of the forms $a^j$ where $j \in \mathbb{Z}$. We argue that each $a^j$ can be written as $a^{j_0}$ were $1\leq j_0\leq k$. Now by the division algorithm $j = qk + j_0$ where $0 \leq |j_0| < k$. Therefore, $a^j = a^{qk + j_0} = a^{j_0}$. If $j_0>0$ then $1\leq j_0 < k$ and so we have brought $a^j$ to the form $a^{j_0}$. If $j_0 < 0$ then $- k< j_0 < 0 \implies 0 < k+j_0 < k$. But $a^{j_0} = a^{k+j_0}$. Thus, we have brough $a^j$ to the form $a^{k+j_0}$, the desired form. Finally, if $a^{j_1} = a^{j_2}$ if and only if $j_1=j_2$ where $1\leq j_1,j_2 < k$. This is because $a^{j_1-j_2} = e$ and so $j_1 - j_2 \equiv 0(\bmod k)$ which forces $j_1=j_2$. Thus, $[a] = \{ a^j | 1\leq k \leq j , (k,j) = 1\}$. Hence, $|[a]| = \phi (k)$. This means $|A| = r\phi(k)$. Therefore, $\phi (k)$ divides $|A|$.