Let p be a prime number and let a be an integer that is not

Let p be a prime number and let a be an integer that is not divisible by p. Then { [1]p,[2]p.........[p-1]p} = {[a.1]p,[a.2]p,.......[a.(p-1)]p} (Hint: Note that the map is a one-to-one and onto. , A=B means A subset of B and B subset of A)

Solution

since a is not divisibe by p

for 1<=r<p

a.r is not divisible by p

So [a.r] = [m] for some 1<=m<p

then the function is defined on S = {[1],...[p-1}]

by f([x]) = f([a.x])

takes elements of S to S.

now this map is one one

for if

f([x]) = f([y])

then [ax] = [ay]

so [a.(x-y)] = [0]

=> [x-y] = [0]

so [x] = [y]

since the cardinality of domain and codomain is same proving one-one is sufficient to show range = codomain =completeset

we can prove it onto

we have [a^-1] = [n] for some 1<=n<p

now for any 1<=r<p

we have f([a^-1r]) = [a.a^-1r] = [r]

so function is onto