Results 1 to 7 of 7

Math Help - Permutation help

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    somewhere
    Posts
    6

    Permutation help

    Okay, please let me know if I am on the right track here, any help is very much appreciated. Keep in mind that I am NOT a Math major, so please assume I am not a super wiz on terminology and what not. Thanks.


    Let m be a positive integer less than 17. Consider the function fm from Z17 to Z17 defined by fm(x) = m*x mod 17.
    1. Show that fm is one-to-one (and thus a permutation) - This is where I need help the most
    2. Determine the disjoint cycle form of f7
    3. Determine if f7 is an even permutation
    4. Determine the disjoint cycle form of f4
    5. Determine if f4 is an even permutation


    1) So one-to-one means that we must show that it is "injective". Thus, we must show that arbitrary inputs (say a and b) under the same operation in the function must be equal to each other (not sure if I worded this properly)


    i.e.
    f(x) = x - 5
    Let a and b be real numbers such that f(a) = f(b)
    f(a) = a - 5 = b - 5 = f(b)
    a - 5 = b - 5
    a = b
    f is injective


    So using what know, would we pick three arbitrary values (1 for m and 2 for x)?:
    fm(x) = m*x mod 17
    Let a, b, and d be arbitrary values such that fa(b) = fa(d)
    fa(b) = a*b mod 17 = a*d mod 17 = fa(d)
    a*b mod 17 = a*d mod 17

    Since 17 is a prime number, it will be relatively prime to a no matter the value and a is positive (a>0), so we get:
    a*b mod 17 = a*d mod 17
    -> b mod 17 = d mod 17

    I'm not sure where to go from here. I know that the mod function under multiplication in a finite set is closed under the operation and non-repetitive (no two inputs have the same output). But I'm not sure what property to point to or what not to show this. Help here is appreciated.

    2 and 3) Here I would show the disjoint cycle form and break it down into disjoint cycles of size 2, and if there are an even amount, it's even, if odd, then it's odd. The only help I need here is can you help me in breaking it up into cycles of 2?
    f7(x) = 7x mod 17
    So the disjoint cycle form is: (1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5)
    How do I break this into cycles of 2?

    Answering the above will help me with the rest. So if you guys could help me out, that would be awesome! Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Permutation help

    Quote Originally Posted by spawn8214 View Post
    1) So one-to-one means that we must show that it is "injective". Thus, we must show that arbitrary inputs (say a and b) under the same operation in the function must be equal to each other (not sure if I worded this properly)
    Inputs [...] must be equal? No, that's not right. Phrasing it in English is a nice exercise, so I recommend trying again.

    Quote Originally Posted by spawn8214 View Post
    i.e.
    f(x) = x - 5
    You mean, e.g.

    Quote Originally Posted by spawn8214 View Post
    Let a, b, and d be arbitrary values such that fa(b) = fa(d)
    fa(b) = a*b mod 17 = a*d mod 17 = fa(d)
    a*b mod 17 = a*d mod 17

    Since 17 is a prime number, it will be relatively prime to a no matter the value and a is positive (a>0), so we get:
    a*b mod 17 = a*d mod 17
    -> b mod 17 = d mod 17

    I'm not sure where to go from here.
    Isn't b mod 17 = d mod 17 what you were supposed to prove, i.e., isn't it the end of the proof of injectivity? What you are writing is correct, though I am not sure you you showed why the facts that a and 17 are relatively prime and a*b mod 17 = a*d mod 17 imply that b mod 17 = d mod 17, i.e., why a can be canceled.

    Quote Originally Posted by spawn8214 View Post
    So the disjoint cycle form is: (1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5)
    How do I break this into cycles of 2?
    Any cycle (x1, x2, ..., xn) equals the composition of n - 1 transpositions (x1 x2)(x2 x3) ... (xn-1 xn). Therefore, a cycle of length n is even iff n is odd.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    somewhere
    Posts
    6

    Re: Permutation help

    Isn't b mod 17 = d mod 17 what you were supposed to prove
    Don't I have to show that b=d? So there has to be something to show that b mod 17 = d mod 17 -> b = d

    I am not sure you you showed why the facts that a and 17 are relatively prime and a*b mod 17 = a*d mod 17 imply that b mod 17 = d mod 17, i.e., why a can be canceled.
    Wouldn't this be because we can split a*b mod 17 into a mod 17 * b mod 17

    Then if a and 17 are relatively prime, then a mod 17 just equals a, so we can divide both sides by a
    Last edited by spawn8214; April 17th 2013 at 02:42 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Permutation help

    Quote Originally Posted by spawn8214 View Post
    Don't I have to show that b=d? So there has to be something to show that b mod 17 = d mod 17 -> b = d
    You are proving injectivity of fm. What is its domain? It's ℤ17 = {0, ..., 16}. For all b ∈ ℤ17, b mod 17 = b.

    Quote Originally Posted by spawn8214 View Post
    Wouldn't this be because we can split a*b mod 17 into a mod 17 * b mod 17

    Then if a and 17 are relatively prime, then a mod 17 just equals a, so we can divide both sides by a
    I am not sure why the same reasoning does not work when the ring is modulo a number that is not prime, e.g., ℤ16 and a is not relatively prime with 16, e.g., a = 8. Besides if a and 17 are relatively prime, it does not follow that a mod 17 = a. Take, e.g., a = 18.

    Hint: The real reason is the ability to divide by a.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2013
    From
    somewhere
    Posts
    6

    Re: Permutation help

    I am not sure why the same reasoning does not work when the ring is modulo a number that is not prime, e.g., ℤ16 and a is not relatively prime with 16, e.g., a = 8. Besides if a and 17 are relatively prime, it does not follow that a mod 17 = a. Take, e.g., a = 18
    I get what you are saying. I'm trying to point to some sort of property or theorem or something that says in this case I can divide by a. I know I can because a is the same on both sides (obviously) and any two numbers with the same divisor can be simplified by dividing by the divisor (in other words: x * z = x * y. Since x is a divisor of both sides, we can simplify the sides by dividing by x). How can I show this formally?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Permutation help

    The general fact is that in ℤn, xy = xz implies y = z for x that are relatively prime with n. This is because by the Bézout's identity, there exist integers u and v such that ux + vn = d where d is the greatest common divisor of x and n, i.e., d = 1. Viewed in ℤn, ux + vn = 1 becomes ux = 1, i.e., u is the multiplicative inverse of x. Thus, if xy = xz, we can multiply both sides by u and get (ux)y = (ux)z, i.e., y = z.

    As you said, since 17 is prime, every nonzero element of ℤ17 is relatively prime with 17, and thus every element has a multiplicative inverse. This means that one can divide in ℤ17, i.e., ℤ17 is not just a ring, but a field, and many familiar laws from rational or real numbers carry over to ℤ17.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2013
    From
    somewhere
    Posts
    6

    Re: Permutation help

    Okay, that makes sense; connects the dots. Thank you, I think I have everything I need to put together a formal proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is this a permutation?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2010, 12:40 PM
  2. permutation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 27th 2010, 03:53 PM
  3. Permutation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 17th 2010, 04:17 PM
  4. Permutation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 7th 2008, 11:01 AM
  5. even or odd permutation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: June 19th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum