Let $(a_n)$ be a strictly increasing sequence of positive integers such that: $a_2 = 2$, $a_{mn} = a_m a_n$ for $m, n$ relatively prime. Let $(a_n)$ be a strictly increasing sequence of positive integers such
  that: $a_2 = 2$ and $a_{mn} = a_m a_n$ for $m, n$ relatively prime. Show that $a_n = n$, for every positive integer $n$.


This is a result apparently due to Paul Erdős, and supposedly has a proof by induction.

I tried like this, $a_{10}=a_2a_5$. After this what we can do?



[Editor's comment]
Possibly due to the apparent simplicity of the conditions it may be difficult to appreciate the subtleties of this question. If we try and construct a counterexample like $a_3=4$, $a_4=5$, $a_5=6$, then the requirements dictate $a_6=8$, $a_{10}=12$, $a_{15}=24$. At this point we realize that we have been speeding. For monotonicity forces $a_9\le 11$, and therefore $a_{18}\le22&lt;a_{15}$, violating the requirements. It is not obvious why something similar ruins all the modifications to the sequence $a_n=n$.
[/comment, JL]
For those thinking that this question is blatantly obvious via prime factorization : see the attempt below by another user, who has left it as an answer, for what goes wrong.


Yes, this problem can be done by induction, with some playing around. I quote the solution that I found in "Putnam and Beyond" by Gelca and Andreescu, but with gaps for those interested to fill, which I'll give in hints with answers hidden. On a side note, I did search for a duplicate on this site, but could not find one.




Why is $a_1 = 1$?



   Either observed from monotonicity of $a_n$ , or $a_2=a_2a_1$ for example.



Why is $a_3 = 3$? First, why is $a_{15} &lt; a_{18} &lt; 2a_{10}$?



   The first is by monotonicity, the second using the fact that $a_{18} = a_2a_9 = 2a_9 &lt; 2a_{10}$.



Use the properties of $a$ to conclude that $a_3 &lt; 4$, therefore equalling $3$.



    From above, $a_{15} = a_3a_5 &lt; 2a_2a_5 &lt; 4a_5$, so $a_3 &lt; 4$.



Show that $a_4=4,a_5=5$.



   Since $a_6 = a_2a_3 = 6$, we have $a_3=3&lt;a_4&lt;a_5&lt;a_6=6$, giving the answers.



That was a flavor of things to come, and gives a good idea of what to do : use multiples of two!





Suppose $k&gt;6$ and $a_j=j, \forall j &lt; k$. Assuming I find a $l \geq k$ such that $a_l=l$. Why is $a_k = k$ then?



   Monotonicity, of course : we have $$k-1 = a_{k-1} &lt; a_{k} &lt; a_{k+1} &lt; ... &lt; a_{l-1} &lt;a_l=l$$ so the only way of squeezing them all in is that $a_p=p$ for each $p$ in the middle.



The idea is to search for $l$ which can be decomposed into two co-prime factors clearly smaller than $k$. Let $l$ be "the smallest even number greater than or equal to $k$ which is not a power of $2$". Show that $l-k \leq 3$. 



   Well, two of $k,k+1,k+2,k+3$ are even, and both of those can't be powers of two, since no powers of $2$ differ by $2$ other than $2$ and $4$, which can't belong to the collection as $k&gt;3$. So the (smaller in case both aren't powers) one that isn't a power of two then qualifies for $l$.



Show that $a_l=l$. Conclude the problem.



   Well, $l$ is not a power of two, so we write $l = 2^r m$, with $m$ odd. Note that $r&gt;0$, now use $k&gt;l-4$ to conclude that $2^r &lt; k$ and $m &lt; k$.Therefore, $a_l = a_{2^r}a_{m} = 2^rm = l$.




More is true : call a function $f :\mathbb N \to \mathbb R$ multiplicative if $f(1)=1$ and $f(m)f(n) = f(mn)$ for all $m,n$ co-prime.Erdos proved that any increasing multiplicative non-constant function is of the form $n^{\alpha}$ for some $\alpha &gt; 0$. Our case is $\alpha = 1$, of course.
You can prove it by induction on $n$ if you prove first that it is true for all prime numbers. 

$n=2$ is true because $a_2=2$, so we can hypothesis that $a_j=j$ for each $j&lt;n$ and we want prove that $a_n=n$.

If $n$ is prime, then $a_n=n$.
If $n$ is not prime,  we can factorize $n$ as 

$n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$

but $p_k^{\alpha_k}$ is coprime with respect the other members so 

$a_n=a_{p_1^{\alpha_1}\dots p_{k-1}^{\alpha_{k-1}}}a_ {p_k^{\alpha_k}}= a_{p_1^{\alpha_1}\dots p_{k-1}^{\alpha_{k-1}}} p_k^{\alpha_k}=$

$=\dots= p_1^{\alpha_1}\dots p_k^{\alpha_k}=n$