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.


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

| cite | improve this answer | |

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.