0
$\begingroup$

Let $p$ be prime and define $f : \mathbb{Z}_p \to \mathbb{Z}_p$ by $f([x])=[ax],a\in\mathbb{Z},p\nmid a$. Prove that $f$ is 1-to-1 and onto.

The question is equivalent to proving that $f$ permutes the elements of $\mathbb{Z}_p$. I know that proving that $f$ is invertible will prove that $f$ is one-to-one, but I'm not sure how to do this. Also, I know I'll have to use some properties of congruences modulo primes.

$\endgroup$
  • $\begingroup$ Since the set is finite, it is enough to prove 1-to-1. If $f([x])=f([y])$, then $[ax]=[ay]$. This means that $a(x-y)$ is divisible by $p$. Since $p$ is prime and doesn't divide $a$ it follows that $p$ divides $x-y$. This means that $[x]=[y]$. $\endgroup$ – conditionalMethod Oct 20 at 4:20
1
$\begingroup$

If $f([x]) = f([y])$ then $[ax] = [ay]$, thus $p|(ax-ay) \implies p|a(x-y) \implies p|(x-y) \implies [x] = [y]$ then $f$ is $1-1$

Now let $[x] \in \mathbb{Z}_{p}$

We have that $(p,a) = 1$ then there exists $s,t \in \mathbb{Z}$ such that $1 = as + pt$ thus $p|(1-as)$ $\implies [as] = [1] \implies [x] = [asx] = f([sx])$ then $f$ is onto

$\endgroup$
1
$\begingroup$

Right.

So $\operatorname {gcd}(a,p)=1$. Thus there exist $b,c$ such that $ba+cp=1$. That is $b\cong a^{-1}\pmod p$. So $f^{-1}([x])=[bx]$. You can check that $f^{-1}$ is a well-defined inverse for $f$. Thus $f$ is invertible, hence bijective.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy