This is a problem out of Rosen's number theory book

Show that if $n$ is an integer then $$\pi(n)=\sum\limits_{j=2}^{n}\left[\frac{(j-1)!+1}{j}-\left[\frac{(j-1)!}{j}\right]\right].$$

For $n \neq 4$ I understand that $(n-1)!\equiv 0 \mod n$ for composite $n$. Following the proof: $$\left[\frac{(n-1)!+1}{n}-\left[\frac{(n-1)!}{n}\right]\right]=\left[\frac{1}{n}\right]=0 .$$

I don't understand why that equals $0$. Is there something special about the bracket notation?

For $n=4$, I see why this equals $0$.

  • 1
    $\begingroup$ The bracket notation $[ x ]$ in general implies the largest integer $\leq x$. Therefore, you see that $\big[ \frac{1}{n} \big] = 0$ for $n > 4$. However, check with the notation followed in that particular book. $\endgroup$ – Singhal Feb 21 '14 at 8:07
  • $\begingroup$ Do you know Wilson's theorem? $\endgroup$ – Konstantinos Gaitanas Feb 21 '14 at 9:55

If $j$ is prime, then we know from Wilson's theorem that $j|(j-1)!+1$.
Let $\frac{(j-1)!+1}{j}=F$
We can see that if $j$ is prime then $\lfloor F \rfloor =F$ and $\lfloor\frac{(j-1)!}{j}\rfloor=F-1$ and so their difference is exactly $1$.
On the other hand if $j>4$ is composite then $\lfloor F \rfloor - \lfloor\frac{(j-1)!}{j}\rfloor=0$

So, the above formula is a sum of $1$'s for every prime not exceeding $n$ and that explains the result $\pi(n)$.


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.