Design and Prove a Bijection from $\mathbb{Z}^1 \to \mathbb{Z}^2$

Question

I'm trying to implement a program and have come across the following problem and would like to see how much discrete math I recall. I'm mapping m objects to a square 2D grid and I'd like for the mapping to be unique, which I translate as "Given a square grid of side length N and m objects, design a bijection between each object and a unique ordered pair of coordinates."

If my notation is correct, this is a transformation $T: \mathbb{Z}^1 \to \mathbb{Z}^2$. I've been suggested that $T(x) = (x//n, x \% n)$ will work and I'd like to prove this.

I need to first show that $T: V \to W$ is surjective which means $Im(T) = W$ which I can show by:

1. $\forall w \in W, \exists v : T(v) = w$

2. is this equivalent to: $Im(T) \subseteq W \land W \subseteq Im(T)$?

To show (1) means to show any ordered pair integers can be generated from an integer $\iff$ $\exists x : T(x) = (z_1, z_2)$.

I said let $x = z_1N + z_2$ and then T($z_1N + z_2$) = $((z_1N + z_2) // N, (z_1N + z_2) \% N) = (z_1, z_2)$ where I'm assuming the mod operator and floor division operators are distributive?

Then I need to prove T is injective which means if $T(x_1) = (N//x_1, N\%x_1) = T(x_2) = (N//x_2, N \% x_2) \implies x_1 = x_2$

I thought about considering equating each component but wasn't sure how that helped me. Now I'm considering the approach that if the ordered pairs are equal $\implies Nx_1 + x_1 = Nx_2+ x_2$ to which I get $-N(x_2 - x_1) = x_2 - x_1$ but here I am stuck.

Any pointers and verifications are appreciated!

Answer 1

I'm assuming from the context that $m=N^2$, that $V = \{0,\dots,m-1\}$, and $W = \{0,\dots,N-1\}^2$. Also you have an $n$ in the definition of $T$ and I think you mean $N$.

Your answer to (2) is correct. You need to show $T(x) \in W$ for each $x \in V$, and for each $y$ in $W$ there exists $x \in V$ such that $T(x) = y$. The fact that $T(z_1N+z_2) = (z_1,z_2)$, and the injectivity of $T$, comes from a theorem called (among other things) the Division algorithm:

Given two integers $a$ and $b$ with $b>0$, there exist unique integers $q$ and $r$ such that $0 \leq r < b$ and $$ a = bq + r $$

This theorem rests on the Well-ordering Principle: A nonempty set of positive integers has a minimum element.