0
$\begingroup$

If gcd$(a,n)=1$, then multiplication by $a$ defines a bijection from $\mathbb{Z}_n-\{0\}$ to itself.

My working:

If $n=p$ a prime, then we can use the Fermat's Little Theorem. If $n$ is not prime in general, I tried the following:

$x\equiv0,1,2,\ldots,n-1$ (mod $n$), then $ax\equiv0,a,2a,\ldots,(n-1)a$ (mod $n$).

Since gcd$(a,n)=1$, we can cancel $a$ on both sides to get back $x\equiv0,1,2,\ldots,n-1$ (mod $n$).

My doubts:

I think my working is wrong. I know what we need to do is to show that all the elements after multiplied by $a$ have different remainders modulo $n$. But I am not sure what theorems to use, I only know some basic elementary number theory theorems. Can we solve this problem by using any simple methods?

Thanks for the help!

$\endgroup$
1
$\begingroup$

Sketch:

  • Step $1$: Prove that the map $x\mapsto ax$ is injective. Suppose that $ax\equiv ay\pmod n$, then $ax=ay+kn$, so $a(x-y)=kn$. Therefore, $n\mid a(x-y)$. Since $a$ is relatively prime to $n$, $n\mid x-y$ and $x\equiv y\pmod n$.

  • Step $2$: Prove that the map $x\mapsto ax$ is surjective. Let $z\in(\mathbb{Z}/n)^\times$ Since $a$ and $n$ are relatively prime, there exist $x$ and $y$ so that $ax+ny=1$. Consider $xz$: under this map, $zx$ maps to $axz=(1-ny)z=z-nyz\equiv z\pmod n$. Since $z$ is nonzero, $xz$ must also have been nonzero.

One could also use that $(\mathbb{Z}/n)^\times$ is a finite set and injectivity or many other techniques. Also, $(\mathbb{Z}/n)^\times$ is just another way to write the set that you describe.

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