The relation $(m,n) \mapsto 2^{m-1}(2n-1)$

Question

Show that relation $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\mathbb{N}\times\mathbb{N}$ on $\mathbb{N}$.

Can anyone explain how to show this?

Answer 1

It is clear that such relation is a function.

Let $k$ be an arbitrary positive integer and let $k=2^{a_1}\cdot3^{a_2}\cdots p_t^{a_t}$be its prime factorization, where $p_i$ is the $i$-th prime and $a_i$ is the largest integer $e$ for which $p^e\mid k.$ Then $3^{a_2}\cdots p_t^{a_t}$ is odd. You should be able to continue from here to show that the function is onto.

The fact that the function is a one-to-one correspondence follows from the uniqueness of the prime factorization of an integer or from Euclid's lemma: If $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c.$

Answer 2

Let $N$ be a natural number. Then, by the unique prime factorization, one can show that if $N$ is odd, we can find a unique $n$ such that $N=2n-1$ and in that case $m=1$. Similarly, if $N$ is even, then, again by unique prime factorization, one can show that $\exists m,n\in \mathbb{N}$ such that $N=2^{m-1}(2n-1)$. This shows that the mapping is bijective.

Answer 3

Prove that for every $k\in\mathbb N$ there are $m,n\in\mathbb N$ such that $k=2^{m-1}(2n-1)$ (surjectivity), and secondly that this combination $\langle m,n\rangle$ is unique (injectivity).

Example: $k=672=2^5\times 21$ (first write all factors $2$; then the second factor is odd). Here $m=6$ and $n=11$.