Results 1 to 3 of 3

Math Help - Permutation Mapping Proof

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    Permutation Mapping Proof

    Prove that the mapping \pi (i) = 328 i \mod 2011 is a permutation of S_{2011}.

    Attempt:
    I think to prove this I have to show that both one-to-one and onto properties hold:

    For one-to-one, suppose \pi(i_1)=\pi(i_2)

    328 i_1 \mod 2011 = 328 i_2 \mod 2011

    Now how do I simplify this to get i_1 =i_2?

    To prove it's Onto, I think I have to show that evey i has an image under \pi. So, how do I need to "show" that \pi(i) = 328 i \mod 2011=j for some j?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by demode View Post
    Prove that the mapping \pi (i) = 328 i \mod 2011 is a permutation of S_{2011}.

    Attempt:
    I think to prove this I have to show that both one-to-one and onto properties hold:

    For one-to-one, suppose \pi(i_1)=\pi(i_2)

    328 i_1 \mod 2011 = 328 i_2 \mod 2011

    Now how do I simplify this to get i_1 =i_2?

    To prove it's Onto, I think I have to show that evey i has an image under \pi. So, how do I need to "show" that \pi(i) = 328 i \mod 2011=j for some j?


    2,011 is a prime number so 328 (as is any other natural number under 2,011) is invertible modulo 2,011, thus...

    After you have 1-1, onto follows at once since you've a finite set.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    in general, the map a-->na (mod p) is a bijection when 0 < n < p, and p is prime.

    why? (Zp,+) is cyclic of prime order, so any non-identity element is an (additive) generator.

    so a-->na is an element of Aut(Zp), automorphisms are bijective.

    a more elementary argument: suppose 328a = 328b (mod 2011).

    then 328(a - b) = k(2011) for some integer k.

    without loss of generality, we can assume 0 ≤ b ≤ a < 2011.

    now 2011 is prime, and it divides k(2011), so it either divides 328 or a - b. since 2011 obviously does not divide 328,

    it must divide a - b. but 0 ≤ a- b < 2011 - b < 2011 and the only number 2011 divides between 0 and 2010 (inclusive) is 0.

    so a - b = 0, and a = b.

    the fact that the set of congruence classes modulo 2011 is finite, then shows that π is also surjective.

    (ok, technically we've shown that π permutes the set {0,1,2...,2010}, but this set has the same cardinality as {1,2,....,2011},
    just "re-name the elements being permuted")
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof, bijective aplication and conformal mapping
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 19th 2011, 12:44 PM
  2. Complex open mapping & conformal mapping problems.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 22nd 2011, 08:26 AM
  3. Permutation proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 27th 2010, 08:02 AM
  4. need help in this permutation proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 22nd 2008, 11:09 AM
  5. Mapping Proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 1st 2008, 12:21 AM

Search Tags


/mathhelpforum @mathhelpforum