Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am doing some olympiad exercises and have difficulties with the following one:

Consider a sequence $a_1,a_2,...$ which is strictly monotonically increasing and $a_1,a_2,...\in\mathbb N$

Now I know that $a_2=2$ and $a_{xy}=a_xa_y$ if $\gcd(x,y)=1$

I would like to show that $a_n=n$

The first thing I did was to write down the first values $a_1,2,a_3,a_4,a_5,2a_3,...$

Now I think it is necessary to separate cases where n is odd and even but I have no idea how to do it, may you could help me.

EDIT: As discussed in the comments, it seems the sequence $a_n=n$ is not unique, but I would like to prove $a_n=n$ using my assumptions, no matter if it is unique or not. If you see a different explicit formula I would also be interested in.

share|cite|improve this question
up vote 2 down vote accepted

Let $f(x)=a_x$. The strict monotonicity hypothesis can be rewritten as $f(j)-f(i) \geq j-i$ for any $i<j$.

Denote by $\Omega$ the set of all integers $x \geq 1$ such that $f(x)=x$. Since $f$ is strictly monotonic, $\Omega$ is “convex” : if $a<b$ are in $\Omega$ then all the integers between $a$ and $b$ are in $\Omega$ also.

Also, $\Omega$ is weakly multiplicative : if $a,b\in \Omega$ are coprime, then $ab\in \Omega$.

We have $f(15)=f(3)f(5)$ and $f(18)=2f(9)$, so $2f(9) \geq f(3)f(5)+3$ by strict monotonicity. On the other hand, $f(10)=2f(5)$ and hence $2f(5) \geq f(9)+1$ by strict monotonicity. Combining those two inequalities,

$$ 4f(5) \geq 2f(9)+2 \geq f(3)f(5)+5 \gt f(3)f(5) $$

This implies $4 \gt f(3)$, so $f(3)=3$ and hence $3\in \Omega$.

So $6=2\times 3 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,6\in \Omega$ yields $[2,6] \subseteq \Omega$ since $\Omega$ is convex.

So $15=3\times 5 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,15\in \Omega$ yields $[2,15] \subseteq \Omega$ since $\Omega$ is convex.

So $42=3\times 14 \in \Omega$ since $\Omega$ is weakly multiplicative.

Then $2\in \Omega,42\in \Omega$ yields $[2,42] \subseteq \Omega$ since $\Omega$ is convex.

More generally, if we define a sequence $(u_k)$ by $u_1=5$ and $u_{k+1}=3u_k-1$ then by induction, every $u_k$ is in $\Omega$, qed.

UPDATE (in answer to a comment) Here is how the induction works :

Suppose $u_k \in \Omega$. As $u_k$ is congruent to $2$ modulo $3$, it is coprime to $3$, so $3u_k \in \Omega$ since $\Omega$ is weakly multiplicative. Then $2$ and $3u_k$ are both in $\Omega$, so $[2,3u_k] \subseteq \Omega$ since $\Omega$ is convex. In particular, $3u_k-1 \in \Omega$, i.e. $u_{k+1} \in \Omega$. So $\Omega$ contains all the $u_k$ and finally $\Omega$ contains all the positive integers.

share|cite|improve this answer
Thank you for your help, could you explain the last part a little bit more in detail? Why $u_1=5$? – Alexander Mar 26 '13 at 16:26
@Alexander : you can take $u_1=2$ if you prefer. Please see my edit above – Ewan Delanoy Mar 26 '13 at 16:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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