Kürschâk and Nagel’s theorems (Erdos 1932)

Consider the familiar reciprocal sums

$\displaystyle \begin{aligned} &\frac11+\frac12+\frac13+\cdots+\frac1{n-1}+\frac1n,\\ &\frac1{m+1}+\frac1{m+2}+\frac1{m+3}+\cdots+\frac1{m+n-1}+\frac1{m+n},\\ &\frac1{m+k}+\frac1{m+2k}+\frac1{m+3k}+\cdots+\frac1{m+(n-1)k}+\frac1{m+nk},\\ &\frac{a_1}{m+1}+\frac{a_2}{m+2}+\frac{a_3}{m+3}+\cdots+\frac{a_{n-1}}{m+n-1}+\frac{a_n}{m+n}, \quad (a_i,m+i)=1\ \end{aligned}$

None of the above quantities are integers.The first, second, and fourth cases all follow from one very elementary principle. One looks for a prime $p$ which occurs in one denominator more strongly than it occurs in every other denominator. After the fractions are put over a common denominator, every term except one acquires a factor of $p$ . The exceptional term does not. Thus the numerator cannot be divisible by $p$ , while the denominator is divisible by $p$ . No cancellation can remove that prime from the denominator. The right language for “occurs more strongly” is the $p$ -adic valuation, the largest exponent $e$ such that $p^e$ divides the number.

So the guiding question is not merely whether some denominator has a prime factor that the others lack. What we really seek is a denominator containing a prime to a strictly higher power than every other denominator. Once such a denominator has been found, no cancellation can make the reciprocal sum integral.The third has the same final mechanism, but finding the relevant prime power becomes a deeper problem about the arithmetic of a finite progression. Thus every proof below has the same shape: locate one denominator with an isolated maximal prime-power contribution

Proofs:

For the first expression, look at the largest prime- when we clear denominators, the denominator is divisible by this prime and numerator is not.

Look among the denominators $1,2,\ldots,n$ for the largest power of $2$ dividing any of them. There is exactly one denominator with that largest power of $2$ . To see this, suppose two different denominators had the same maximal valuation $e$ . They would have the form $2^e u, 2^e v,$ where $u<v$ are odd. Since two distinct odd integers differ by at least $2$ , the integer $2^e(u+1)$ lies strictly between them. But $u+1$ is even, so this intervening integer is divisible by $2^{e+1}$ . That contradicts the maximality of $e$ . Hence one denominator has strictly larger $2$ -adic valuation than all the others.

Exactly the same argument works for every finite block of consecutive denominators: $\frac1{m+1}+\frac1{m+2}+\cdots+\frac1{m+n}.$ The interval $m+1,\ldots,m+n$ again has a unique member divisible by the largest power of $2$ occurring anywhere in the interval. Thus the sum is not an integer.

For the second expression, if the $n$ is smaller then $m$ then the quantity is less than one, otherwise there will be a prime between $m$ and $2m$ (Some weak versions of Prime Number Theorem like Betrand Postulate is enough to see that)- and now again taking common denominators, we see that denominator is divisible by largest prime in that interval and the numerator is not. This proof is useful conceptually, but the highest-power-of-two proof is more uniform and does not need information about primes in intervals.

Same argument even for the fourth expression. Choose the unique denominator $m+j_0$ with maximal $2$ -adic valuation. In particular, $m+j_0$ is even. The condition $(a_{j_0},m+j_0)=1$ forces $a_{j_0}$ to be odd. Thus, after multiplication by the least common denominator, every term except the $j_0$ -th term is even, while the $j_0$ -th term is odd. The numerator of the resulting fraction is odd and the denominator is even. Therefore the sum is not an integer. The coprimality condition is exactly the right hypothesis. It says that a coefficient cannot secretly contain the prime power which protects its denominator. Without this condition, the exceptional term could lose the obstruction by cancellation.

For the third expression, the intended proof is still the same: find one term whose valuation at some prime is larger than the valuation of that prime in every other term. But the automatic power-of-two argument can fail. For example, when $k=2$ and $m=1$ , all denominators are odd: $3,5,7,\ldots,2n+1.$ So one cannot simply repeat the previous proof with $p=2$ .

There is one useful case in which the power-of-two method still works immediately. If $k$ is odd, then multiplication by $k$ preserves the pattern of residues modulo powers of $2$ .The genuine difficulty begins when the common difference has an even part.

First remove the common factor of $m$ and $k$ . Writing $\displaystyle m=gm_0$ and $\displaystyle k=gk_0$ , with $\displaystyle (m_0,k_0)=1$ , merely multiplies every denominator by the same number $g$ . This adds the same prime factors to every denominator and does not affect which denominator has the largest power of a given prime. Thus one may assume from the start that $\displaystyle (m,k)=1$ .

Now take a prime $p$ which divides one denominator. Then $p$ cannot divide $k$ . Indeed, were $p$ to divide both $k$ and $m+jk$ , it would divide $jk$ as well; subtracting would show that it divides $m$ . That contradicts $(m,k)=1$ . This matters because two terms of the progression differ by $(m+ik)-(m+jk)=(i-j)k.$ Suppose that a large prime power $p^e$ divides both of them. Since $p$ does not divide $k$ , it must divide the index difference $i-j$ . More exactly, $p^e$ divides $i-j$ . But the indices lie between $1$ and $n$ , so their nonzero difference has size at most $n-1$ . Therefore, if $p^e>n,$ that same power cannot divide two distinct denominators. It is automatically isolated. The problem is therefore reduced to finding such a distinguished prime power.

Assume, for a contradiction, that no denominator contains a prime power larger than $n$ . Consider the factorial-normalized product $\ Q:=\frac{(m+k)(m+2k)\cdots(m+nk)}{n!}.$ Every factor in this product can be written as $\frac{m+jk}{j}=k+\frac{m}{j}>k.$ Therefore $\displaystyle Q>k^n\ge4^n.$

We next show that the assumption about prime powers forces the opposite inequality. To do this, one studies the product $(m+k)(m+2k)\cdots(m+nk).$ because it stores every prime power occurring in every denominator. To understand how much of a prime $p$ occurs in this product, one asks separately: how many terms are divisible by $p$ ? How many by $p^2$ ? How many by $p^3$ ? Since $p$ does not divide $k$ , the terms divisible by $p^\ell$ occur at indices spaced exactly $p^\ell$ apart. This is why the pattern resembles the familiar pattern of multiples of $p^\ell$ in $1,2,\ldots,n.$ The factorial $n!$ records that ordinary pattern. Comparing the progression product with $n!$ tells us how prime-power divisibility in the progression differs from the ordinary baseline.

Under the contradictory assumption, if $\displaystyle p^r\le n<p^{r+1},$ then no denominator contributing to $Q$ is divisible by $p^{r+1},$ so, after dividing $P$ by $n!$ , at most one extra factor of $p$ can remain from each level $p^\ell, l \le r$ . There are only $r$ relevant levels. So after reducing $Q$ to lowest terms, its numerator contains at most $r$ factors of $p$ . Thus that numerator is at most $T(n):=\prod_{p^r\le n}p,$ where each prime occurs once for every power not exceeding $n$ . Put $b_i=\lceil n/2^i\rceil,$ stopping when $b_i=1.$ Since the intervals $(b_i,2b_i]$ cover ${2,\ldots,n},$ every prime power $p^r\le n$ lies in one of them. If $b<p^r\le2b,$ then $p\mid\binom{2b}{b},$ because $(2b)!$ has one more multiple of $p^r$ than the two copies of $b!;$ moreover, two powers of the same prime cannot both lie in $(b,2b],$ since their ratio is at least $2.$ Hence $\displaystyle T(n)\le\prod_i\binom{2b_i}{b_i}.$ By induction we can see this product is less than $4^n.$ But the earlier argument gave $Q>4^n,$ whereas $Q$ is at most its reduced numerator, which is at most $T(n).$ This contradiction proves that a required prime power exists.