SILK ROAD MATHEMATICS COMPETITION XVII

From the statement we have $$\tau (n{a}_{n+1}^n+(n+1)a_n^{n+1})⊢n.(1)$$ Let $a_1=1$ and $a_2=2$. Suppose that we have constructed the numbers $a_1,a_2,\dots ,a_m$ so that they are different natural numbers and (1) satisfied for each $n=1,2,\dots ,m-1$. Let $L$ be the smallest positive integer that does not occur among the numbers $a_1,a_2,\dots ,a_m$. We set $a_{m+2}=L$ and choose $a_{m+1}$ so that $a_{m+1}>a_1+a_2+\cdots +a_m+L$ and (1) is true for $n=m$ and $n=m+1$. Repeating this process we obtain a permutation of all positive integers satisfying (1) for any positive integer $n$.

For a prime $p$ and a positive integer $k$, we denote by ${\psi }_p(k)$ the largest integer $l$ such that $k$ is divisible by $p^l$.

Lemma. Given positive integers $a,b,k,l,M$. Then there is a prime number $p>M$ and a positive integer $x$ such that ${\psi }_p(a{x}^k+b)=l$.

Proof. Let $d=M+k+b$ and $p$ be a prime divisor of $a{b}^{k-1}(d!{)}^k+1$. Then $p>d>M$. By induction on $N$, we prove that for any positive integer $N$ there exists a positive integer $x$ such that the number $a{x}^k+b$ is divisible by $p^N$.

Base: for $N=1$ the number $x=d!b$.

Suppose that for $N$ there exist positive integers $x$ and $t$ such that $a{x}^k+b=p^{N}t$. Let $z$ be a positive integer such that the number $a{x}^{n-1}zk+t$ is divisible by $p$ (such a number exists, since the number $p$ is coprime with $d!a$, and hence with the number $akx$). Then $$\begin{array}{rl}a(x+z{p}^N{)}^k+b& \equiv a{x}^k+a{x}^{k-1}z{p}^{N}k+b\equiv p^{N}t+a{x}^{k-1}z{p}^{N}k\\ & \equiv p^N(a{x}^{k-1}zk+t)\equiv 0(\mathrm{mod}{p}^{N+1}),\end{array}$$ and the induction step is proved.

Therefore, there are positive integers $x,t$ with $a{x}^k+b=p^{l+1}t$. Then $$a(x+p^l{)}^k+b\equiv a{x}^k+a{x}^{k-1}pk+b\equiv a{x}^{k-1}k{p}^l(\mathrm{mod}{p}^{l+1}),$$ i.e. ${\psi }_p(a(x+p^l{)}^k+b)=l$, and the lemma is proved.

From the lemma for $a=m,b=(m+1)a_m^{m+1},M=1,k=m,l=m-1$ there is a prime $p>1$ and a positive integer $x$ such that ${\psi }_p(m{x}^m+(m+1)a_m^{m+1})=m-1$ and from the lemma for $a=m+2,b=(m+1)k^{m+1},M=p,k=m+2,l=m$ there is a prime $q>p$ and a positive integer $y$ such that ${\psi }_q((m+1)k^{m+1}+(m+2)y^{m+2})=m$. By the Chinese remainder theorem, there is a positive integer $z$ such that $z>a_1+a_2+\cdots +a_m+L,z\equiv x(\mathrm{mod}{p}^m)$ and $z\equiv y(\mathrm{mod}{q}^{m+1})$. Then it is easy to see that $a_{m+1}=z$ works.