Proving that $f(n,m) = 3^n5^m$ is injective.

Question

The function $f:\mathbb{N}\times \mathbb{N}$ is defined by

$$f(n,m) = 3^n5^m$$

Determine if it is surjective and/or injective.

It isn't surjective, because $2$ in the codomain has no preimage.

As for injective... I could not think of a counterexample, so I guess it is. However, I failed to prove that. My attempt was something like:

Have some $(a,b),(c,d) \in \mathbb{N}\times \mathbb{N}$: $$f(a,b) = f(c,d)$$

$$3^a5^b=3^c5^d$$

$$\frac{3^a}{3^c}=\frac{5^b}{5^d}$$

$$\textrm{some mathematical voodo here}$$

$$a =c \land b = d$$

The intended proof is incomplete and/or wrong or it isn't actually injective.

How can I determine whether this function is injective?

@AymanHourieh: Of couurseeee.. No, I fear not. I will check it out, thank you. — Saturn, Nov 09 '13 at 15:54
Omega, compare the fundamental theorem of arithmetic with the following question: would the map $f(n,m) = 2^n 4^m$ be injective? Would the map $f(n,m) = 2^n 3^m$ be? What about $50^n 11^m$? — snar, Nov 09 '13 at 16:00

score 1 · Answer 1 · answered Nov 09 '13 at 16:26

You were close:

$$3^a5^b=3^c5^d\iff 3^{a-c}=5^{d-b}\iff a-c=d-b=0\iff (a=c)\;\wedge\;(b=d)$$

Now, the second double implication follows at once from the Fundamental Theorem of Arithmetic...though, of course, if you rely on the FTA then you can "jump" from the first equality to the last part.

score 0 · Answer 2 · answered Nov 06 '17 at 22:35

Maybe my answer is wrong, but let's give it a try anyway. We'll try do prove the injectivity by induction.

Lets take pairs of $n$ and $m$ belonging to the set $\{0,1,2\}$. In that case, we get that $f(0,0) = 1$, $f(0,1)=5$, $f(1,0) = 3$, $f(1,1) = 3\cdot5=15$, $f(1,2) = 3\cdot5^2 = 75$, $f(2,1) = 3^2\cdot5=45$, $f(2,2) = 3^2\cdot5^2=225$. As we can see, this condition holds true because 3 and 5 are coprimes.

We can see that for those initial values, each pair $f(m,n)$ was different from each other.

Now, let's assume that for each value of $x$ and $y$; $1\le x\le m$ and $1\le y \le n$, the hypothesis holds true, that is, that the function is injective for each value of $x$ and $y$ until $m$ and $n$.

Now, let's try to see what happens with values of $m+1$ and $n+1$:

$f(m+1,n) = 3^{m+1}\cdot 5^n = 3\cdot3^m\cdot5^n$

$f(m,n+1) = 3^{m}\cdot 5^{n+1} = 5\cdot3^m\cdot5^n$

$f(m+1,n+1) = 3^{m+1}\cdot 5^{n+1} = 15\cdot3^m\cdot5^n$

Since $f(m+1,n) \neq f(m,n+1) \neq f(m+1,n+1)$, we have that the function is injective for $n+1$ and $m+1$ and, therefore, by induction, is injective for any pair $n,m$. The key factor here is, again, the fact that both values are coprime, and if they cannot share any common integer between them, for $m+1$ and $n+1$, they won't be able to share it for any $n$ and $m$.

Proving that $f(n,m) = 3^n5^m$ is injective.

2 Answers2