# 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, violating the requirements. It is not obvious why something similar ruins all the modifications to the sequence $$a_n=n$$. [/comment, JL]

• If you're stuck in a problem like this, just try something. For instance, set $a_3=4$, and otherwise give as low value as you can to any term ($a_4=5,a_5=6,a_6=8$, and so on). See what goes wrong. Try to fix it. See what goes wrong. Try a different $a_3$. See what goes wrong. Now look for a pattern in the wrongs. Commented Aug 23, 2019 at 6:20
• This is a pleasantly non-standard question, and some effort should be made to save it. If you are new to this kind of questions it is, indeed, difficult to see what you can try. In such a case you should try and give other kinds of context. Such as, where did you encounter this problem? Commented Aug 30, 2019 at 17:45
• @JyrkiLahtonen It is a duplicate of Growing sequence of $a_n$, which is a much more well-written question. Commented Feb 7, 2020 at 4:49
• @YuiToCheng I agree this is not well written. Anyway, your suggested duplicate is not a duplicate. If you assume that the rule $a_ma_n=a_{mn}$ holds for all pairs $(m,n)$, then the question is IMO trivial. When we only require that condition when $\gcd(m,n)=1$, the asker there is unmounted at the first fence for we cannot conclude that $a_4=4$. Commented Feb 7, 2020 at 4:55
• The question also appeared here. And similar to the 6th problem from the Polish National Olympiad from 2010, see the AoPS link. Commented Feb 7, 2020 at 11:25

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} < a_{18} < 2a_{10}$$?

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

• Use the properties of $$a$$ to conclude that $$a_3 < 4$$, therefore equalling $$3$$.

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

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

Since $$a_6 = a_2a_3 = 6$$, we have $$a_3=3, 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>6$$ and $$a_j=j, \forall j < 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} < a_{k} < a_{k+1} < ... < a_{l-1} 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>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>0$$, now use $$k>l-4$$ to conclude that $$2^r < k$$ and $$m < 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 > 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 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$$

• Yes, this is what I thought, but there's a problem : what if $n=3$? You can't conclude that $a_3=3$ because after factorization you just get $a_3 = a_3a_1 = a_3$ which is no information! Commented Aug 23, 2019 at 6:57
• @астонвіллаолофмэллбэрг You’re right, we must prove it first for all prime numbers Commented Aug 23, 2019 at 6:58
• @FedericoFallucca After proving it for all prime numbers, we can just use monotonicity ($a_7 = 7, a_{11} = 11$, there isn't room for $a_9\neq 9$ in a strictly monotonous sequence). However, "proving it for all prime numbers" is not so easy a task that you can just assume that it's don. And what you really assume here is that it is proven for all prime powers. That's different. Also, it's not in any way the easiest way to solve the problem. After showing $a_3 = 3$, monotonicity along with $a_{2n} = 2a_n$ for odd $n$ is enough. Commented Aug 23, 2019 at 7:18
• You’re right! I leave the answer for what people that can think that can they do it in this way. Commented Aug 23, 2019 at 7:21