# discrete one to one function proof [closed]

Prove the following function is one to one function $$f : \mathbb N\times \mathbb N \to \mathbb N ,\quad f( i , j ) = 2^i3^j$$

-

## closed as off-topic by egreg, user1337, TZakrevskiy, Stefan Hamcke, anortonDec 18 '13 at 19:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – egreg, user1337, TZakrevskiy, Stefan Hamcke, anorton
If this question can be reworded to fit the rules in the help center, please edit the question.

What have you tried for this problem? We need more context to see where you are getting stuck. –  Brian Scholl Dec 18 '13 at 18:10
tried many times but no luck :\ –  user2862699 Dec 18 '13 at 18:12
@user2862699 What did you try in those attempts? –  T. Bongers Dec 18 '13 at 18:12
I've put values for i and j and try substituting –  user2862699 Dec 18 '13 at 18:15

Hints:

$$2^i3^j=2^n3^m\iff 2^{i-n}=3^{m-j}$$

Suppose $\;i\ge n\;$ , then the left side in the last equality above is an integer. Use now the Fundamental Theorem of Arithmetic....

-
Do we really even need the Fundamental Theorem of Arithmetic for this? Couldn't we just argue by divisibility? –  Brian Scholl Dec 18 '13 at 18:13
Formally, @BrianScholl? I'm not sure...yet the FTA is rather basic and sometimes it is even covered in high school, so I don't think it is a heavy weapon. But perhaps there's another way to do it formally . –  DonAntonio Dec 18 '13 at 18:15
@BrianScholl: We certainly need something to assure us that $3^{m-j}$ doesn't have an alternate factorization involving a bunch of $2$'s. –  Austin Mohr Dec 18 '13 at 18:16
Precisely my point, @AustinMohr . Thanks. –  DonAntonio Dec 18 '13 at 18:17
still didn't get it :\ –  user2862699 Dec 18 '13 at 18:26

Hint $\ f$ is $1$-$1$ iff $f(a,b) = f(c,d) \Rightarrow (a,b)=(c,d),\$ i.e. $\ 2^a 3^b = 2^c 3^d\Rightarrow a=c, b=d$

This is an immediate consequence of the uniqueness of prime factorizations. If you can't use that then prove this: if $m,n$ are odd and $\,2^a m = 2^c n\,$ then $a = c\$ (hint: cancel $2$'s then use parity). Applying this above, we can cancel $\,2^a = 2^c$ to obtain $\,3^b = 3^d,\,$ so $\,b = d$.

-

$$F(i_1,j_1)= F(i_2,j_2) \implies 2^{i_1}3^{j_1} = 2^{i_2}3^{j_2} \implies \dots \implies i_1=i_2,\,j_1=j_2 .$$

-
This is what the OP has to prove, and I can't see how this helps him to do so, even by hint... –  DonAntonio Dec 18 '13 at 18:16
@DonAntonio: the definition of one to one $F(X_1)=F(X_2)\implies X_1=X_2$. –  Mhenni Benghorbal Dec 18 '13 at 18:18
I don' think that was the OP's problem, @Mhenni but how to prove that. –  DonAntonio Dec 18 '13 at 18:19