Results 1 to 6 of 6

Math Help - Euler's theorem proof help

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    47

    Euler's theorem proof help

    Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

    1. Prove for any n: If x,y are in \Phi_n , then xy \ mod \ n is also in \Phi_n, using a contrapositive argument.

    2. Prove: Every a \in \Phi_n has an inverse modulo n in \Phi_n , by considering the linear congruence ax \equiv 1 (mod \ n)

    3. Prove: For every a \in \Phi_n the function f_a : \Phi_n \to\Phi_n defined by f_a(x) =ax is a permutation.

    I really don't know what to do for these.
    Any help would be greatly appreciated.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Nguyen View Post
    Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

    1. Prove for any n: If x,y are in \Phi_n , then xy \ mod \ n is also in \Phi_n, using a contrapositive argument.

    2. Prove: Every a \in \Phi_n has an inverse modulo n in \Phi_n , by considering the linear congruence ax \equiv 1 (mod \ n)

    3. Prove: For every a \in \Phi_n the function f_a : \Phi_n \to\Phi_n defined by f_a(x) =ax is a permutation.

    I really don't know what to do for these.
    Any help would be greatly appreciated.

    Thanks

    It's be great if you'd tell us what in the world do you call \Phi_n to...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by Nguyen View Post
    Hey, I am having a difficult time trying to prove a few statements relating to Euler's Theorem.

    1. Prove for any n: If x,y are in \Phi_n , then xy \ mod \ n is also in \Phi_n, using a contrapositive argument.

    2. Prove: Every a \in \Phi_n has an inverse modulo n in \Phi_n , by considering the linear congruence ax \equiv 1 (mod \ n)

    3. Prove: For every a \in \Phi_n the function f_a : \Phi_n \to\Phi_n defined by f_a(x) =ax is a permutation.

    I really don't know what to do for these.
    Any help would be greatly appreciated.

    Thanks
    i believe is the set of all positive integers (including 1) relatively prime to n.
    For the first one:
    given that so there exist integers such that . similarly there exist integers such that . Multiplying the two equations we have:
    .


    The second part follows again from the fact that if then there exist integers such that . Note that . hence is the you want.

    for the third one you need to show that is bijective. can you do it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    hint for number 3: \Phi_n is a finite set. therefore you only need to show that f_a is surjective (why?)

    now use part (2).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2010
    Posts
    47
    Sorry Tonio, \Phi_n = \{x: 1 \le x < n, gcd(x,n)=1 \}


    Quote Originally Posted by abhishekkgp View Post
    i believe is the set of all positive integers (including 1) relatively prime to n.
    For the first one:
    given that so there exist integers such that . similarly there exist integers such that . Multiplying the two equations we have:
    .


    The second part follows again from the fact that if then there exist integers such that . Note that . hence is the you want.

    for the third one you need to show that is bijective. can you do it?
    Thanks abhishekkgp, I fully understand the first one now. Is that all the working for the second one? I think I understand it.

    I can see that for the third one, that it is surjective and because the set is finite it is therefore bijective, but I don't get how to work it out properly.

    Any help here?

    Thanks so much for your help.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    a permutation of \Phi_n IS a bijection on \Phi_n. and you know that f_a is a surjection why? this is where part (2) comes in.

    if for every a, we have an x with ax = 1 (mod n), then suppose y is any (arbitrary) element of \Phi_n.

    what is f_a(xy)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. One more Euler theorem proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 7th 2009, 10:54 AM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 10:07 AM
  4. Euler's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 19th 2008, 06:47 AM
  5. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 05:19 PM

Search Tags


/mathhelpforum @mathhelpforum