Thread: relatively prime

By counting an appropriate geometric arrangement of points, prove that (PLEASE SEE IMAGE) if p and q are relatively prime.

Follow the Gauss' 4th proof of Quadric Reciprocity.
(Eisenstein Version).

im sorry but i dont understand how to use the recipocrity proof to answer this question. please help.

Hello, demon1!

The statement is not true . . .

. . . . . . . . . . . . .q-1
We have: .2(p/q) ∑ i . = . 2(p/q)·q(q-1)/2 . = . p(q - 1)
. . . . . . . . . . . . .i=1

Originally Posted by Soroban

Hello, demon1!

The statement is not true . . .

. . . . . . . . . . . . .q-1
We have: .2(p/q) ∑ i . = . 2(p/q)·q(q-1)/2 . = . p(q - 1)
. . . . . . . . . . . . .i=1

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)

The meaning of "[ ]" is the greatest integer function.

"Oh ... that's different . . . Never mind."

. . . . Emily Litella, 1982