How to prove surjectivity of $f:\{1,\ldots,n\}\to\Bbb Z_n,\,k\mapsto[k]$? Alternative proofs for $|\Bbb Z_n|=n$?

Question

Im trying to prove that $\Bbb Z_n:=\Bbb Z/n\Bbb Z$ have cardinality $n$ just using properties of rings, this mean that Im trying to do it without the use of any multiplicative inverse $z^{-1}\in\Bbb Q$.

My try: if $|\Bbb Z_n|=n$ then must exist a bijective function of the kind

$$f:\{1,\ldots,n\}\to \Bbb Z_n$$

The easiest candidate is $f$ such that $f(k)=[k]$, where $[k]$ is the equivalence class of $k$, defined by

$$[k]=k+n\Bbb Z$$

Then two elements of $a,b\in\{1,\ldots,n\}$ are equivalent if

$$a\sim b\iff a\in b+n\Bbb Z\iff a-b\in n\Bbb Z$$

Then I can show that $f$ is injective, i.e. if $a,b\in\{1,\ldots,n\}$ and $a\neq b$ then $[a]\neq[b]$ due to the fact that

$$(a-b\in n\Bbb Z\iff b-a\in n\Bbb Z)\iff (|a-b|> 0\implies |a-b|\in n\Bbb N_{>0})$$

Then if $|a-b|\in n\Bbb N_{>0}$ we have that

$$|a-b|\le nk,\quad(\forall k\in\Bbb N_{>0})\land(\forall a,b\in\{1,\ldots,n\})$$

Because $\Bbb N_{>0}$ is well ordered to prove the last statement is enough to show that

$$|a-b|<n=\min(n\Bbb N_{>0})$$

(I dont will write this proof here, it is unnecessary to me at this point).

The questions: the problem that I have is that I dont know how to show that $f$ is surjective if I restrict myself to not use things like $z^{-1}\in\Bbb Q$ or any division rule. So,

1. there is an easy way to show the surjectivity of $f$? In fact,

2. there is an easier way to prove that $|\Bbb Z_n|=n$?

Thank you in advance!

Answer 1

For any $k \in \mathbb{Z}$, there exist unique $q,r \in \mathbb{Z}$ with $k-1 = qn + r$ and $0 \le r \le n-1$. So, $k = qn + (r+1)$ with $1 \le r+1 \le n$. This defines a function $g \colon \mathbb{Z} \to \{1,...,n\}$ by $k \mapsto r+1$. It is clear that $g$ is constant on each coset of $n\mathbb{Z}$, so $g$ descends to a function $\bar g \colon \mathbb{Z}/n\mathbb{Z} \to \{1,...,n\}$. Using the fact that $g(k) = k$ for all $k \in \{1,...,n\}$, it is easy to check that $f$ and $\bar g$ are inverses, so $f$ is a bijection.

Answer 2

Concisely:

• $x\neq y$ lie in the same equivalence class $\iff (x-y)\in n\mathbb{Z}-0\implies\vert x-y\vert \ge n$
• But if $x\neq y\in\{1,2,\cdots,n\}$, then $\vert x-y\vert \le n-1$.
• So, the elements of $\{1,2,\cdots,n\}$ map to distinct cosets, and so there are at least $n$ cosets.
• It is clear that there are at most $n$ cosets, and so we are done.

Answer 3

I appreciate the other answers but I think this auto-answer fit better the requirements that I want.

An alternative an simpler way is: to show that $|\Bbb Z_n|\le n$ notice

$$(an+b)+n\Bbb Z=b+n\Bbb Z\implies an+n\Bbb Z=n\Bbb Z,\forall a\in\Bbb Z$$

If we show that for any fixed $z\in\Bbb Z$ and any fixed $n\in\Bbb N_0$ then there is a unique solution $a,b$ for

$$z=an+b$$

such that $a\in\Bbb Z$ and $b\in\{0,\ldots,n-1\}$ we are done (*).

Proof by contradiction: suppose exist $b_1\neq b_2$ and $b_1,b_2\in\{0,\ldots, n-1\}$ where for some fixed $n\in\Bbb N_0$ the above statement holds.

Because $\Bbb Z$ is an ordered ring we can assume WLOG that $b_1<b_2$ then $an+b_1<an+b_2$. Then

$$a_1n+b_1=a_2n+b_2\implies a_1\neq a_2$$

Because $b_1<b_2$ and $b_1,b_2\in\{0,\ldots, n-1\}$ then $c:=b_2-b_1\in\{0,\ldots, n-1\}$. Then we can rewrite

$$n(a_1-a_2)=c$$

what is impossible for $c<n$ due to the order axioms and theorems of any ordered ring(**).$\Box$

(*) We can show that any $an+c$ can be reduced to an expression $an+b$ with $b<n$ and non-negative.

(**) This can be shown easily by induction over $|a_1-a_2|$.