# Proving that $\pi(n)=\sum\limits_{j=2}^{n}[\frac{(j-1)!+1}{j}-[\frac{(j-1)!}{j}]]$ when $n$ is an integer

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

• 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. – Singhal Feb 21 '14 at 8:07
• Do you know Wilson's theorem? – 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)$.