larry hammick

Let p and q be relatively prime odd numbers >0. In the real plane consider a
triangle whose vertices are
( 0, q/2 )
( p/2, 0 )
( p/2, q/2 ).
Show that there are an even number of lattice points inside that triangle.

This theorem won't win an Abel Prize, but in the Easy To State And Hard To
Prove category, it's worth at least a cigar. AFAIK it has appeared
previously only at sci.math (where it defeated everybody) and on a strong
math forum in Rumania.

LH

einar_andreas_rødland

I think I have the solution.

First, lets rephrase the problem as follows:
For p,q>0 odd and relatively prime, consider the set of odd
points---i.e. (i,j) with i,j odd integers---inside the triangle T(p,q)
having corners (0,0),(p,0),(0,q). The number of odd points in T(p,q) is
then even.

Let's assume p<q.

Consider the triangle T' with corners (p,0),(0,q),(0,q-2p). There are no
odd points on the edges of this triangle. For a given odd j, the number
of odd i with (i,j) inside the triangle must be even: the line segment
(x,y) inside the triangle with y=j has length 2*(p-j) which is a
multiple of 4 for j odd and must therefore contain an even number of odd points.
If q>2p, we can remove T', reducing the original triangle T(p,q) to
T(p,q-2p). Since T' has an even number of odd points, T(p,q) has an even
number if and only if T(p,q-2p) has.

If q<2p, T' may be seen as composed of T(p,q) plus T(p,2p-q) (mirrored
around the x-axis). Since T' has an even number of odd points, T(p,q)
has an even number if and only if T(p,2p-q) has.

Reducing (p,q) to (p,abs(q-2p)) will continue until we reach (p,q)=(1,1)
(or (1,q) suffices), in which case the number of odd points inside is zero.

Einar

fred the wonder worm

Let T(p,q) denote the number of lattice points inside the appropriate
triangle. Note that the statement is trivially true if either p or q
is 1, as there are no lattice points inside the triangle. (i.e.,
T(p,1) = T(1,q) = 0.)

For integral k with 0 < k < q/2 there are Floor(1/2 + k*p/q) lattice
points inside the triangle on the line y = k. So the total number of
lattice points is

Sum(k = 1 to (q-1)/2) Floor(1/2 + k*p/q)
WLOG let p > q > 1. We can then write p = 2*q*t + u for integers t, u
satisfying t > 0, |u| < q, u odd, gcd(q,u) = 1. The inner term of the
sum becomes

Floor(1/2 + k*(2*q*t + u)/q)
= Floor(1/2 + 2*k*t + k*u/q)
= 2*k*t + Floor(1/2 + k*u/q)

Since we are concerned only with parity, we can drop the even terms as
being of no interest. T(p,q) thus has the same parity as

F_q(u): Sum(k = 1 to (q-1)/2) Floor(1/2 + k*u/q).

and the result will be proved if we can show that this is even for all
appropriate choices of q, u.

Now, Floor(1/2 + x) + Floor(1/2 - x) = 0, except when x is an odd
multiple
of 1/2. Since q is odd, k*u/q can never be an odd multiple of 1/2.
Thus
F_q(u) + F_q(-u) = 0, and in particular they have the same parity. So
it
suffices to consider positive values of u.

So we want to show that F_q(u) is always even for positive u, coprime
to q,
with 0 < u < q. But F_q(u) = T(u, q), which is a smaller instance of
the
problem. The result follows by descent, height induction, or the
usual
proof by contradiction ("consider the smallest counterexample...").

Cheers,
Geoff.

-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ftww@maths.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------

If p=q=7 there are 6 points in the triangle so gcd(p,q)=1 is not
necessary (it is sufficient). More generally the number of lattice
points in the triangle is even if and only if gcd(p,q)=+1 or -1 mod 8

Stewart

larry hammick

"Einar Andreas Rødland"

Very nice. I saw how to reduce it to the case p<q<2p, but I got no further
in that direction. Eventually I came up with a proof akin to the one here:
http://www.mathlinks.ro/Forum/viewtopic.php?t=148026
Larry