Is this elementary number theory proof correct?

Question

Let $A(n)$ be the number of primes less than $n$, divided by $n$ (so for example, $A(n) \leq 1$, as there cannot be more primes less than $n$ as there are integers less than $n$). Suppose that $n$ is a positive multiple of the positive integer $q$. Show that $$A(n) \leq \frac{q+(n-q)\frac{\phi({q})}{q}}{n}$$

This is what I have done.

First note that the above is equivalent to showing that (no. of primes $<n$) $\leq {q+(n-q)\frac{\phi({q})}{q}}$

Let $n=kq$

Therefore (no. of primes $<n$) $=$ (no. of primes $<kq$) $\leq \phi(kq)$ (remember $1$ is not prime)

$\phi(kq)=\phi(k)\phi(q) \leq (k-1)\phi(q)$ as $\phi(k) \leq (k-1)$.

$(k-1)\phi(q) < q+(k-1)\phi(q)=q+(qk-q)\frac{\phi(q)}{q}=q+(n-q)\frac{\phi(q)}{q}$ as required.

The reason I'm worried about this is that I have actually established a stricter inequality than in the question. However, I can't see anything wrong with this. Any reassurance or criticism would be much appreciated.

Answer 1

You do not know that $(n/q,q)=(k,q)=1$, so you don't know that $\phi(qk)=\phi(q)\phi(k)$. Let me shine some light on a line of reasoning that involves just counting numbers.

Split the set $\{1,\cdots,kq\}$ into $k$ strings of consecutive integers,

• $I_0=\{1,\cdots,q\}$
• $I_1=\{q+1,\cdots,2q\}$
• $I_2=\{2q+1,\cdots,3q\}$
• $\cdots$
• $I_{k-1}=\{(k-1)q+1,\cdots,kq\}$

Note that each interval contains exactly $q$ numbers and is a full system of representatives for the residues mod $q$. Anyway, let $A\subseteq\{1,\cdots,kq\}$ containing all of $I_0$, and for $i>0$, $A$ contains all those elements of $I_i$ that are coprime to $q$. Now, $iq+r$ is coprime to $n$ iff $r$ is coprime to $n$, so in fact $\#(I_i\cap A)$ is equal to the number of elements in $I_0$ coprime to $q$, which is $\phi(q)$. Hence

$$|A|=|I_0|+\sum_{i=1}^{k-1}|I_i\cap A|=q+(k-1)\phi(q).$$

Observe that $k-1=(n-q)/q$ and the set of all primes contained in the interval $\{1,\cdots,kq\}$ is a subset of $A$, so the $\#$ of primes is $\le |A|$. One motivation behind treating $I_0$ differently than $I_i$ for positive $i$ is that $q$ may be prime, but $q$ is not coprime to $q$, so $q\in I_0$ but $q$ is not in the subset of $I_0$ of elements coprime to $I_0$, suggesting $I_0$ requires special treatment.

You are right in thinking that this is a crude bound, though. (In fact, this bound grows linearly with $n$, as it is of the form $a+bn$, whereas $\pi(n)\sim n/\log n$ by the prime number theorem.)