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
2
$\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

Not the answer you're looking for? Browse other questions tagged or ask your own question.