Thread: Permutation Mapping Proof

Prove that the mapping is a permutation of .

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

For one-to-one, suppose



Now how do I simplify this to get ?

To prove it's Onto, I think I have to show that evey has an image under . So, how do I need to "show" that for some j?

Originally Posted by demode

Prove that the mapping is a permutation of .

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

For one-to-one, suppose



Now how do I simplify this to get ?

To prove it's Onto, I think I have to show that evey has an image under . So, how do I need to "show" that 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

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")