# Math Help - Permutation help

1. ## 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!

2. ## Re: Permutation help

Originally Posted by spawn8214
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.

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

Originally Posted by spawn8214
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.

Originally Posted by spawn8214
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.

3. ## 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

4. ## Re: Permutation help

Originally Posted by spawn8214
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.

Originally Posted by spawn8214
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.

5. ## 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?

6. ## 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.

7. ## 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.