Proving that $f$ is a bijection from $N$x$N$ to $N$. I am having trouble with the following problem: 
$f: N\times N\rightarrow N$ and $f(i,j)=2^{i-1}(2j-1)$. Prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent. 
Work: I am told that Euclid's Lemma will be useful to proving injection and also that for any positive integer $n$, $n$ is a product of prime numbers. 
For injection, I set $f(a,b)=f(x,y)\rightarrow 2^{a-1}(2b-1)=2^{x-1}(2y-1)$. 
Then I distributed across to get $2^ab-2^{a-1}=2^xy-2^{x-1} \rightarrow 2^ab-2^xy=2^{a-1}-2^{x-1} \rightarrow 2(2^{a-1}b-2^{x-1}y)=2^{a-1}-2^{x-1}$. 
From here, I am unsure how to apply Euclid's Lemma to arrive at the injection result. 
I am even more unsure how to prove surjection. 
 A: Since $2b-1$ and $2y-1$ are odd, they will never be powers of $2$. So $2^{x-1} = 2^{a-1}$, which implies that $a = x$. Divide $2^{x-1}$ and $2^{a-1}$ out. You are left with an equation giving you $y = b$. 
A: We don't need to use prime factorization here; the deepest fact that we need is that there is no integer that is both even and odd.
Suppose $2^{a−1}(2b−1)=2^{x−1}(2y−1)$. Without loss of generality, $a\le x$; so we can divide both sides by $2^{a−1}$ and obtain $2b-1 = 2^{x-a}(2y-1)$ (note that $2^{x-a}$ is an integer by our assumption). If $a<x$, then $2^{x-a-1}$ is still an integer, and so the right-hand side is $2\cdot 2^{x-a-1}(2y-1)$ which is even; but the left-hand side is odd, which is a contradiction. Therefore $a=x$, which gives $2b-1=2y-1$ and so $b=y$ as well.
A: Hint : To prove surjectivity, notice that $j$ will produce the odd numbers when $i=1$. Also, notice that every even number is either of the form $2^n$ for some natural $n$ or of the form $2^k m$ for some natural $k$ and odd $m$.
