Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Happened to get this from a friend.

How does one show that for all pairs of real numbers $x$ and $y$, there is $n \in \mathbb{N}$ such that $$ x < \frac{\Phi(n+2)}{\Phi(n)} < y$$ where $\Phi$ is the Euler's totient function.

$\textbf{Added.}$ This seems to be somewhat related to the problems given here: $\textbf{J 8}, \textbf{J 9}, \textbf{J 10}$ at this link.

share|improve this question
No one pointed out that this is impossible if $x\ge y$? No one pointed out that this is impossible if $y\le0$? –  Gerry Myerson Aug 11 '11 at 7:16
add comment

1 Answer

up vote 11 down vote accepted

Okay, here is an answer assuming plausible conjectures about linear equations in primes.

Lemma: For any real numbers $(a,b)$ with $0 < a < b < 1$, there is a positive integer $n$ such that $\phi(n)/n \in (a,b)$. Moreover, for any integer $k$, we can arrange that $n$ is relatively prime to $k$.

Proof: Let $N$ be larger than $k$, and large enough that $b(1-1/N)>a$. Consider the product $\prod_{p >N} (1-1/p)$, where the product runs over primes greater than $N$. This infinite product is $0$, because $\sum 1/p=\infty$. So there is some $M$ such that $\prod_{N < p < M} p$ is less than $b$. Choose the first such $M$ for which this happens. Then $\prod_{N < p < M} p > b (1-1/M) > a$ by the choice of $M$. Take $n=\prod_{N< p < M} p$. QED

Now, to answer your question. Choose intervals $(a_1, b_1)$ and $(a_2, b_2)$ with $0 < a_i < b_i < 1$ such that $x < a_2/b_1 < b_2/a_1 < y$. Using the lemma, find $n_1$ and $n_2$ such that $\phi(n_i)/n_i \in (a_i, b_i)$, the $n_i$ are both odd, and $GCD(n_1, n_2) = 1$.

Now, if you believe the generalized Hardy-Littlewood conjecture then there are infinitely many pairs $(q_1, q_2)$ of prime numbers such that $n_1 q_1 +2 = n_2 q_2$. For $q_1$ large enough, $n:=n_1 q_1$ has the desired property.

Unfortunately, this equation is one of the ones to which Green and Tao's results do not apply. (In their terminology, $\psi_1$ and $\psi_2$ are linearly dependent.) You might be able to dodge this issue by asking for $q_1$ and $q_2$ to be almost prime rather than prime. (Almost prime meaning a product of two large primes.) I'm not enough of an expert to know whether that trick would work in this setting; if you seriously care about the question, you might try e-mailing Terry Tao.

share|improve this answer
add comment

Your Answer


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