By counting an appropriate geometric arrangement of points, prove that (PLEASE SEE IMAGE) if p and q are relatively prime.
The meaning of "[ ]" means greatest integer function.
----
The idea (which needs some work) is two create the following rectangle: {(0,0),{0,q),{p/2,0},{p/2,q}.
Now draw all the points (integer coefficintes) inside this rectange.
There are (p-1)/2 * (q-1) points.
Now we will count them in a different way.
Draw the line y=p/q*x.
It is easy to see no points lie on this line.
Then find the number of points above and below this rectange. Which I think happen to be the same.
The number of such points (below diagnol) is:
SUM(i=1,q-1) [ p/q* i]
If you double this you get ALL the points.
And by a counting argument we find that:
2*SUM(i=1,q-1)[p/q *i]] = (p-1)/2*(q-1)