Results 1 to 4 of 4

Thread: Again, phi euler function

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    16

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by asub1 View Post
    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$?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    16
    Maybe you mean to say ...
    Yes, im sorry.
    And "$\displaystyle |A|$ " i mean to say #A (the cardinal).

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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|$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 30th 2011, 09:53 AM
  2. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 07:29 AM
  3. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 8th 2010, 02:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: Jan 12th 2010, 05:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 11th 2009, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum