Results 1 to 4 of 4

Math Help - Again, phi euler function

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    16

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

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by asub1 View Post
    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?
    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 " |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
    9
    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|.
    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: November 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: April 8th 2010, 02:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 05:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum