# Again, phi euler function

• Jan 22nd 2009, 03:21 AM
asub1
Again, phi euler function
hi, can anybody prove that?:

Let $\displaystyle G$ finite set.

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

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

($\displaystyle \phi$ is the euler function)

Thanks
• Jan 22nd 2009, 08:52 AM
ThePerfectHacker
Quote:

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

Let $\displaystyle G$ finite set.

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

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

($\displaystyle \phi$ is the euler function)

Thanks

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

Maybe you mean to say $\displaystyle A = \{ a\in G : |a| = k \}$ where $\displaystyle |a|$ is order of $\displaystyle a$?
• Jan 22nd 2009, 10:29 AM
asub1
Quote:

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

Thanks
• Jan 22nd 2009, 11:35 AM
ThePerfectHacker
We will define a relation $\displaystyle \leftrightarrow$ on $\displaystyle A$.
For, $\displaystyle a,b\in A$ define $\displaystyle a\leftrightarrow b$ iff $\displaystyle b = a^j$ for some $\displaystyle j\in \mathbb{Z}$.

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

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

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