First, a lemma Lemma : For any odd prime $p$, there exist positive integers $a, b$ with \[1 < \frac{p^a}{2^b} < \frac{p}{p - 1}\] Proof : The smallest $a$ for which $p^a > 2^b$ is $\lceil b\log_{p}{2} \rceil$ for integer $b$. Since $\log_p{2}$ is irrational, some multiple of it has fractional part arbitrarily close to $1$. Since the desired upper bound is a constant, simply take the appropriate $b$ so that the fractional part is large enough (close enough to $1$) that \[1 < \frac{p^a}{2^b} < \frac{p}{p - 1}\] Let $a_1 = 2^N$ where $N$ will be determined later. Then choose $a, b$ so that \[1 < \frac{3^a}{2^b} < \frac{3}{2}\] and take $a_2 = 2^{N - b}3^a$ whence $a_2 > a_1$ but \[\phi(a_2) = 2^{N - b}3^{a - 1} < 2^{N - 1} = \phi(a_1)\] We can apply this process for as many primes as we like, just by siphoning off powers of two from $a_k$ and turning them into a new prime power in $a_{k + 1}$ so that $a_k < a_{k + 1}$ but $\phi(a_k) > \phi(a_{k + 1})$ (which we can do by our lemma). All we need to do is ensure that there are sufficiently many powers of two in $a_1$ for us to continue our process as long as we like (till $v_2(a_n) > 0$); simply take $N$ sufficiently large.

Let $a_k=p_1*...p_m-p_{n-k}, p_0=1$. Then for big $m$ $\phi(a_k)=a_k(1-\frac{1}{p_{n-k}})\prod_{p|a_k,p>p_m}(1-\frac{1}{p})$. When m is big, second multiple is bigger than \[\frac{1-\frac{1}{p_k}}{1-\frac{1}{p_{k+1}}}.\]

Here's an alternative approach. We use induction on $n$. The base case, $n=1$, is trivial. Now assume we can find positive integers $ a_{1}<a_{2}<...<a_{k} $ such that $ \phi(a_{1})>\phi(a_{2})>...>\phi(a_{k}) $ for some positive integer $k$. Consider positive integers $x$ such that $(x, a_i) = 1$ for all $1 \le i \le k$. Then define $b_i = xa_i$ so $\phi(b_i) = \phi(a_i) \phi(x)$ for all $1 \le i \le k$. If we can find a positive integer $y$ such that $\phi(b_1) < y-1 < y < 2y < b_1$ we are done by Bertrand's Postulate as then there exists $p$ prime such that $p < b_1$ and $\phi(p) = p-1 > \phi(b_1)$. Let $x=q_1 q_2 \cdots q_l$ for some positive integer $l$ where $q_1 < q_2 < \cdots < q_l$ are the consecutive primes greater than the largest prime dividing an $a_i$. Then $\frac{b_1}{\phi(b_1)} > (1 + \frac{1}{q_1-1})(1 + \frac{1}{q_2-1}) \cdots (1 + \frac{1}{q_l - 1}) \ge \frac{1}{q_1} + \frac{1}{q_2} + \cdots \frac{1}{q_l}$ which is diverging as the sum of the reciprocals of the primes $2, 3, 5, \cdots$ is diverging. So such a $y$ must exist and we are done.

goodar2006 wrote: Decreasing Euler's totient function Prove that for each $n \in \mathbb N$ there exist natural numbers $a_1<a_2<...<a_n$ such that $\phi(a_1)>\phi(a_2)>...>\phi(a_n)$. Proposed by Amirhossein Gorzi I think I have a solution and I attached it. (Sorry I couldn't convert it to the convenient form which is common in AOPS website forums.)

Attachments:
solution.pdf (251kb)

It actually can be shown without so much difficulty that for all $n \in \mathbb{N}$ there exist infinitely many $m \in \mathbb{N}$ such that \[ \varphi(m)>\varphi(m+1)>\varphi(m+2)>\ldots>\varphi(m+n) \] Although that, it's a non trivial exercise even for $n=2$; if necessary I'll post the proof below

That is quite fascinating, and does not seem obvious at all. Do you mind posting the proof?

Consider $a_i=p_i^{k_i}, p_n<p_{n_1}<....<p_1, \phi(a_i)=(1-\frac{1}{p_i})a_i$ We can chose $k_i$, suth that $a_1<a_2<...<a_n$ and $\phi(a_1)>\phi(a_2)>...\phi(a_n)$. It is sufficiently $k_1\ln(p_1)<k_2\ln(p_2)<...<k_n\ln(p_n)$ and $k_1\ln(p_1)+\ln(1-\frac{1}{p_i})>...k_n\ln(p_n)+\ln(1-\frac{1}{p_n})$.

hyperbolictangent wrote: That is quite fascinating, and does not seem obvious at all. Do you mind posting the proof? Yes I can post a much stronger result http://leonettipaolo.wordpress.com/fnfn1fn2-for-infinitely-many-n/

Funny solution I found: From $(a_1,...,a_n)$ we jump to $(y\cdot a_1,x \cdot a_1,...,x \cdot a_n)$ where $y=K\cdot A+1$ and $x=(K+1) \cdot A +1$ where $A=a_1\cdot...\cdot a_n$ and $K$ is such that $K>A^2$ and such that $y$ is prime (possible by Dirichlet's). It is trivial to check that $\varphi(y)>\varphi(x)$ using the fact that $\varphi(x) \leq x-\sqrt{x}.$ Edit: We can suppose that $x$ is composite since there are infinitely many composite numbers in sequence $\mathbb N \cdot A +1$

bboypa wrote: It actually can be shown without so much difficulty that for all $n \in \mathbb{N}$ there exist infinitely many $m \in \mathbb{N}$ such that \[ \varphi(m)>\varphi(m+1)>\varphi(m+2)>\ldots>\varphi(m+n) \] Although that, it's a non trivial exercise even for $n=2$; if necessary I'll post the proof below Sorry for reviving a very old thread This problem has intrigued me very much, though i have not been able to solve it and the link given is for a wordpress site that is private. I thought to bump this so that maybe others are able to prove it.