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)$.

  • 2
    $\begingroup$ 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)$. $\endgroup$ – Erick Wong Nov 13 '17 at 7:48
  • $\begingroup$ 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}$? $\endgroup$ – Arin Chaudhuri Nov 13 '17 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Nov 13 '17 at 17:41
  • $\begingroup$ Ah, got it. Thanks! $\endgroup$ – 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 \begin{equation}\tag{1}\sum_{p\leq N} \frac{1}{\ln p} = o(\frac{N}{\ln N})\end{equation}

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.

  • $\begingroup$ 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. $\endgroup$ – Arin Chaudhuri Nov 13 '17 at 6:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Erick Wong Nov 13 '17 at 7:57
  • $\begingroup$ 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. $\endgroup$ – Arin Chaudhuri Nov 13 '17 at 17:37
  • $\begingroup$ @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$. $\endgroup$ – Erick Wong Nov 13 '17 at 21:47
  • $\begingroup$ @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? $\endgroup$ – Erick Wong Nov 13 '17 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.