# $4\mid\phi(n)$ for most $n$

This is from an exercise in LeVeque's Fundamentals of number theory.

Let $N$ be a positive integer. If $f(N)$ denotes the number of positive integers $n \leq N$ such that $4 \not\mid \phi(n)$ then $\lim_{N\to\infty} \dfrac{f(N)}{N}=0.$

My observations so far : since $4\not\mid\phi(n)$ iff $n$ is $1,2,4$ or of the form $p^k$ or $2p^k$ where $p$ is a prime of the form $4m+3$. So it is sufficient to show that $g(N)$: the number of integers $\leq N$ of the form $p^k$ where $p$ is a prime of the form $4m+3$, is $o(N)$.

We have, $$g(N) = \sum_{ \substack{p \leq N\\ p \text{ is prime of the form } 4m+3}} \left \lfloor \dfrac{\ln N}{\ln p} \right\rfloor,$$

but I can't figure out how to show the above is $o(N)$.

• It's sufficient to just show that the number of primes $\le N$ (of the form $4m+3$) is $o(N)$. The contribution from prime powers $p^k$ with $k>1$ is easily bounded by $\sqrt{N} \log_2 N$ (the largest possible value of $p$ times the largest possible value of $k$), which is $o(N)$. – Erick Wong Nov 13 '17 at 7:48
• I don't understand, I can see why the largest possible $k$ is bounded by $\log_2(N)$. But I don't see where the other term comes from. Are you saying the largest possible prime less than $N$ is bounded by $\sqrt{N}$? – Arin Chaudhuri Nov 13 '17 at 17:33
• The largest base for a prime power whose exponent is not $1$ is $\sqrt{N}$. The argument is to show that we only need to consider exponent $1$, i.e. primes. – Erick Wong Nov 13 '17 at 17:41
• Ah, got it. Thanks! – Arin Chaudhuri Nov 13 '17 at 17:44

We can use the inequality $$\pi(n) < C\frac{n}{\ln n}$$ for $n\geq 2$ and some positive constant $C$.

I will show the stronger: $$\sum_{p\leq N} \left \lfloor \frac{\ln N}{\ln p} \right\rfloor= o(N)$$

Note that $$\sum_{p\leq N} \left \lfloor \frac{\ln N}{\ln p} \right\rfloor=\ln N \sum_{p\leq N} \frac{1}{\ln p} + O(\pi(N))$$

Hence it suffices to show $$\tag{1}\sum_{p\leq N} \frac{1}{\ln p} = o(\frac{N}{\ln N})$$

Note that, via summation by parts $$\sum_{p\leq x} \frac{1}{\ln p} = \frac{\pi(x)}{\ln x} +\int_2^x \frac{\pi(t)}{t\ln^2 t} dt \leq \frac{Cx}{\ln^2 x} +C\int_2^x \frac{1}{\ln^3 t} dt$$

A simple application of L'hopitals rule shows that $$\int_2^x \frac{1}{\ln^3 t} dt = o(\frac{x}{\ln x})$$

This shows $(1)$ and completes the proof.

• Is a simpler proof possible? This exercise comes just after the introduction of the $\phi$ function. This inequality has not appeared in the book till then. – Arin Chaudhuri Nov 13 '17 at 6:24
• @ArinChaudhuri Per my comment on the OP, this is roughly equivalent to proving that there are $o(N)$ primes up to $N$. There are various elementary ways to show this, but none that I know of that are as simple as the definition of $\phi$. Perhaps you could provide more details about what facts you are willing to assume. – Erick Wong Nov 13 '17 at 7:57
• What has discussed till now in the book is pretty basic, unique factorization, GCD, LCM, linear Diophantine equations, congruence and residue classes, and the Euler's $\phi-$function. Most problems have not involved techniques far beyond the scope of what has been discussed. – Arin Chaudhuri Nov 13 '17 at 17:37
• @ArinChaudhuri Okay then I guess the most basic approach that I know of is to use a bit of analysis to show that if the number of primes is not $o(N)$ (so there are infinitely many $N$ for which $\pi(N) > cN$), then $\sum 1/p$ diverges. Using that you can show that there exists a sequence of $M$ such that $\phi(M)/M \to 0$, and then it is easy to conclude that the number of primes is $o(N)$ by looking mod $M$. – Erick Wong Nov 13 '17 at 21:47
• @ArinChaudhuri The level of sophistication required is a bit high without any hints or prior similar questions. Is this a “starred” exercise with a higher difficulty? – Erick Wong Nov 13 '17 at 21:48