Maths Olympiad Prep

Track / Stage 4 / 16 of 340 #276 of 1964

Problem 276

AMC 12 late, AIME early
Number theory Difficulty 4.5 Prove it Brazilian Mathematical Olympiad · Brazil

Show that 1+12+13++1n1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} is not an integer for n>1n > 1.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let 2m2^m be the highest power of 22 that does not exceed nn. Then none of the other positive integers less than or equal to nn are divisible by 2m2^m. Let k=lcm(1,2,,n)k = \text{lcm}(1, 2, \dots, n). Now write each of the terms 1,12,,1n1, \frac{1}{2}, \dots, \frac{1}{n} as fractions with denominator kk. All will have even numerators except 12m\frac{1}{2^m} which will have an odd numerator. Thus their sum is a fraction hk\frac{h}{k} with hh odd, so it cannot be an integer.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.