$\varphi(an+b)<kn$ for infinitely many n

64 Views Asked by At

This is a problem from "Problems from the book"

Let $a,b$ be integers greater than $1$. Prove that for any $k>0$ there are infinitely many $n$ such that $\varphi(an+b)<kn$, where $\varphi$ is Euler's totient function.

I think I have a proof for this, but I have two things that bug me about it. One, is I haven't used the condition that $a,b>1$, which pushes me to believe that I fake solved it. Secondly, I haven't really used any nice idea which reinforces my suspicions, but I still can't find where I went wrong.

Sps otherwise that there exists some $n_0$, such that for all $n \ge n_0$, $\varphi(an+b) \ge kn$. Now let $p_i$ be i-th prime greater than $a$. Then we can find $n_1,\dots,n_l$ such that $an_i+b \equiv 0 (mod p_i)$, this follows from the fact that $gcd(a,p_i)=1$. By Chinese Remainder theorem, we can find $u(p_1,\dots,p_l)$ such that $u(p_1,\dots,p_l) \equiv n_i (mod p_i).$ Now, $\prod_{i=1}^l(1-\frac{1}{p_i}) \ge \frac{\varphi(au(p_1,\dots,p_l)+b)}{au(p_1,\dots,p_l)+b} \ge k \cdot \frac{u(p_1,\dots,p_l)}{au(p_1,\dots,p_l)+b} $. Taking the limit as $l$ goes to infinity, and using the fact that $\prod_{p \in \mathbb P} (1-\frac{1}{p})=0$, yeilds a contradiction.

1

There are 1 best solutions below

0
On BEST ANSWER

(1) I think the result (and the proof) hold perfectly well for all positive integers $a$ and all integers $b$ (not just exceeding 1).

(2) I think this idea is a perfectly nice idea! I don't think there's any fundamentally simpler or cleverer approach. My one note would be that you don't need a proof by contradiction: your argument gives a direct construction of a $u$ for which $\phi(au+b) < ku$.