2
$\begingroup$

I have a number theoretic question. Specifically, I am interested in knowing an elementary proof of the following theorem (I used to know it but unfortunately I forgot and can't find it anywhere):

Given $f(n) = 1 + \frac{1}{2} + \frac{1}{3} ... \frac{1}{n}$ and $2^k \leq n < 2^{k+1}$, the largest power of two that divides the reduced denominator of $f(n)$ (i.e. $b$ where $f(n) = \frac{a}{b}$ and gcd($a$,$b$) $=1$) is $2^k$.

$\endgroup$

2 Answers 2

5
$\begingroup$

The denominator of $f(n)$ divides $m=\mathrm{lcm}(1,2,3,\dots,n)$ since $$ s=mf(n)=\sum\limits_{j=1}^n\frac mj $$ is a sum of integers, and $f(n)=\frac{\large s}m$. The least terms denominator will divide $m$.

Since $2^k\le n\lt2^{k+1}$, consider the sum $$ \sum_{j=1}^{2^k-1}\frac1j $$ The largest power of $2$ in the denominator will be a factor of $2^{k-1}$ since $\mathrm{lcm}(1,2,3,\dots,2^k-1)$ is not divisible by $2^k$.

For $2^k\lt j\lt 2^{k+1}$, there are no multiples of $2^k$. Thus, the least terms denominator of $f(n)-\frac1{2^k}$ is not divisible by $2^k$.

Thus, the least terms denominator of $$ \sum_{j=1}^n\frac1j=\underbrace{f(n)-\frac1{2^k}}_{\begin{array}{c}\text{least terms}\\\text{denominator not}\\\text{divisible by $2^k$}\end{array}}+\frac1{2^k} $$ is a multiple of $2^k$.


Another Approach

Consider $m=\mathrm{lcm}(1,2,\dots,n)/2$. $2^{k-1}\mid m$, but $2^k\not\mid m$. For $1\le j\le n$, each term of $\frac mj$ is an integer, except $\frac m{2^k}$. Thus, $$ m\sum_{j=1}^n\frac1j $$ is the sum of $n-1$ integers and one number which is an integer plus $\frac12$.

$\endgroup$
2
  • $\begingroup$ How do you prove your assertion that the largest power of two in the denominator of $\sum_{j=1}^{m}\frac1j$ will be the the largest $k$ such that $1 \leq 2^k \leq m$? $\endgroup$ Apr 3, 2014 at 3:04
  • $\begingroup$ @RenéG: I have added some to the first approach that hopefully clarifies things. Let me know if not. $\endgroup$
    – robjohn
    Apr 3, 2014 at 6:07
3
$\begingroup$

Here's a hint, Ignore the problem. Think about what happens to the power of two of the resultant number when you add together two rational numbers,$\frac{q}{2^kp}+\frac{s}{2^mr}$ where $p,q,s,r$ are all odd.

Use that to prove the theorem inductively.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .