Why is the quotient homomorphism $\phi: \mathbb{Z} \to \mathbb{Z} / (2n + 1) \mathbb{Z}$ injective on the restrictions to $K$?

41 Views Asked by At

Let $K$ be any finite subset of $\mathbb{Z}$. We choose an integer $n \geq 0$ such that $K \subset [-n,n]$. The claim is that the quotient homomorphism $\phi: \mathbb{Z} \to \mathbb{Z} / (2n + 1) \mathbb{Z}$ is injective if we restrict $\phi$ to the set $K$.

Intuitively this makes sense since for any finite subset $K \subset \mathbb{Z}$ can't I always translate the set $K$ by $2n +1$ and then this new set will consist of the unique residue representatives of $\mathbb{Z} / (2n + 1) \mathbb{Z}$. Hence $\phi \mid_K$ has to be injective?

Sorry if my response is not a super formal proof. I was hoping someone can give me a more rational argument than my intuition.

Here is what I was formally thinking:

Suppose that $\phi(k_1) = \phi(k_2)$ for some $k_1, k_2 \in K$, where $\phi(k) = k + (2n + 1) \mathbb{Z}$. Then, there exists some integer $m$ such that $k_1 - k_2 = (2n + 1) m$. Since $k_1, k_2 \in K \subset [-n, n]$, it follows that $|k_1 - k_2| \leq 2n < 2n + 1$, so $m = 0$ and $k_1 = k_2$.

Therefore, $\phi$ is injective when restricted to $K$.

1

There are 1 best solutions below

2
On BEST ANSWER

Define $\phi: \Bbb Z \to \Bbb Z / (2n+1) \Bbb Z$ via $\phi(x) \mapsto (2n+1) \Bbb Z + x$. Then $\phi(x)=\phi(y)$ if and only if $x$ and $y$ are in the same coset of $(2n+1) \Bbb Z$. That can occur only if $x-y \in (2n+1) \Bbb Z$, which can occur only if $(2n+1) \mid (x-y)$.

But since $x, y \in K \subseteq [-n, n]$, we know that $-2n \leq x-y \leq 2n$, so $(2n+1) \mid (x-y) \Rightarrow x-y=0 \Rightarrow x=y$.

This proves $\phi$ is injective when restricted to $K$.