Find the sum of floor function values

Question

For positive integers a, b, show that the sum

∑_m=1^[a/2][bm/a] + ∑_n=1^[b/2][an/b] = [a/2][b/2] + [(a,b)/2].

where the bracket denotes the floor function, i.e. [x] is the greatest integer not exceeding x, and (a,b) is the greatest common divisor of a, b. The first summation runs from 1 to [a/2], the second from 1 to [b/2].

Answer 1

Consider each summand [bk/a] in the first sum on the left side. This is the number of positive integers not exceeding bk/a. In other words, it is the number of lattice points on the half-open segment (A(k,0),D(k,bk/a], where point A is excluded. It is possible that the point D on the diagonal connecting O(0,0) to C(a/2,b/2) is a lattice point. Thus the sum under consideration is equal to the number of lattice points in the rectangle (0,a/2] × (0,b/2] (here written as the direct product of two intervals) below the diagonal OC, with OC included.

Similarly, each summand [ak/b] in the second sum on the left side is the number of lattice points on the half-open segment (A'(0, k),D'(ak/b, k)], with A' excluded but D' included. Thus the second sum on the left side is the number of lattice points in the same rectangle above the diagonal.

Therefore, the two sums on the left side combined is equal to the total number of lattice points in this rectangle, which is [a/2][b/2], plus the number of lattice points on the diagonal, which are counted in each of the sum on the left side. Now we calculate the number of diagonal lattice points. Let d=gcd(a,b), the greatest common divisor of the two integers, we can write a=a'd, and b=b'd, with gcd(a',b')=1. Now sure the point (a',b') is on the diagonal as b'/a'=b/a, which means both (a',b') and (a,b) are on the line y=bx/a, of which the diagonal OC is a part. So are all points (ka',kb') for any positive integer k, among which only those satisfying 1 ≤ k ≤ [d/2] are inside the rectangle. Since gcd(a',b')=1, there are no lattice points between O(0,0) and (a',b'). Consequently, from O(0,0) to C'(a,b)=(a'd,b'd), there are exactly d+1 lattice points including O(0,0). Since the sum under consideration excludes 0's we have to exclude O. So the number of lattice points on OC' (not the diagonal of the rectangle OC) is d. If d is even, which means [a/2]=a/2 and [b/2]=b/2, then the point ([a/2],[b/2]) lies at the upper right corner C of the rectangle and we have exactly d/2 (= [d/2]) lattice points on the diagonal. Othewise we only have [d/2] (< d/2) lattice points. Therefore the sum under consideration is just what we claim to be: [a/2][b/2] + [d/2].