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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Arthur Aug 23 '19 at 6:20
  • 1
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Aug 30 '19 at 17:45

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<a_4<a_5<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>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} <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>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<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$

  • 1
    $\begingroup$ 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! $\endgroup$ – астон вілла олоф мэллбэрг Aug 23 '19 at 6:57
  • $\begingroup$ @астонвіллаолофмэллбэрг You’re right, we must prove it first for all prime numbers $\endgroup$ – Federico Fallucca Aug 23 '19 at 6:58
  • 3
    $\begingroup$ @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. $\endgroup$ – Arthur Aug 23 '19 at 7:18
  • 1
    $\begingroup$ You’re right! I leave the answer for what people that can think that can they do it in this way. $\endgroup$ – Federico Fallucca Aug 23 '19 at 7:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.