After a month of the unexpected break from mathematics, I will resume the regular weekly blog posts. It’s a kind of relaunch of this blog, and I will begin with the discussion of an arithmetic problem with a geometric solution. This is problem 103 from The USSR Olympiad Problem Book:
where is the number of divisors of the natural number .
One can solve this problem by using the principle of mathematical induction or using the fact that the number of integers of the sequence which are divisible by any chosen integer is equal to . The second approach of counting suggests an elegant geometric solution.
Consider the equilateral hyperbola , (of which we shall take only the branches in the first quadrant):
We note all the points in the first quadrant which have integer coordinates as the intersection point of the dotted lines. Now, if an integer is a divisor of the integer , then the point is a point on the graph of the hyperbola . Conversely, if the hyperbola contains an integer point, then the x-coordinate is a divisor of . Hence the number of integers is equal to the number of the integer points lying on the hyperbola . The number is thus equal to the number of absciassas of integer points lying on the hyperbola . Now, we make use of the fact that the hyperbola lies “farther out” in the quadrant than do . The following implication hold:
The sum is equal to the number of integer points lying under or on the hyperbola . Each such point will lie on a hyperbola , where . The number of integer points with abscissa located under the hyperbola is equal to the integer part of the length of the segment [in figure above ]. That is , since , i.e. ordinate of point on hyperbola for abscissa . Thus, we obtain
Caution: Excess of anything is harmful, even mathematics.
I wish to discuss a small problem from The USSR Olympiad Problem Book (problem 59) about the finite sum of harmonic series. The problem asks us to prove that
can never be an integer for any value of .
I myself couldn’t think much about how to prove such a statement. So by reading the solution, I realised that how a simple observation about parity leads to this conclusion.
Firstly, observe that among the natural numbers from 2 to there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to . And the numerator will be an odd number since it’s the sum of even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.