For each positive integer $n$, write the sum $\sum_{m=1}^n 1/m$ in the form $p_n/q_n$, where $p_n$ and $q_n$ are relatively prime positive integers. Determine all $n$ such that 5 does not divide $q_n$.
Problem
Source:
Tags: blogs, number theory, relatively prime, Divisibility Theory
16.10.2007 16:03
$ n=5^k-l,l=1,2,3,4$. Prove by induction.
29.04.2008 23:13
The above answer is not correct. The correct answer, which I am currently providing without full proof, is {1,2,3,4,20,21,22,23,24,100,101,102,103,104,120,121,122,123,124}. Here is a partial proof: Theorem I: If $ \frac{a_i}{b_i}$ are fractions in their lowest terms for $ i=1, 2, 3$, $ \frac{a_1}{b_1}+\frac{a_2}{b_2}=\frac{a_3}{b_3}$ and $ b_1$ is not divisible by 5, then the highest power of 5 dividing $ b_2$ and $ b_3$ are the same. Proof: If 5 is not a factor of $ b_2$, then $ b_3$ is a factor of $ b_1b_2$ and hence not divisible by 5. If, on the other hand $ b_2$ is a multiple of 5, then $ a_2$ is not, and hence $ a_2b_1$ is not, and hence $ a_2b_1+a_1b_2$ is not a multiple of 5. Thus, since $ b_3=\frac{b_1b_2}{\gcd(b_1b_2,a_2b_1+a_1b_2)}$, $ b_3$ and $ b_2$ are divisible by the same powers of 5. Corrolary II: For $ 0\le k\le 4$ and positive integer $ n$, the highest power of 5 dividing the denominator of $ \frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{5n+k}$ is the same as that dividing the denominator of $ \frac{1}{5}+\frac{1}{10}+\ldots+\frac{1}{5n}$ Proof: The integer reciprocals omitted in the latter sum give a fraction whose denominator is not divisible by 5. Corollary III: For $ 0\le k\le 4$ and positive integer $ n$, $ q_{5n+k}$ is not divisible by 5 if and only if $ p_n$ is divisible by 5. Proof: Corollary II states that the highest power of 5 dividing $ q_{5n+k}$ is the same as the highest power of five dividing the lowest-terms denominator of $ \frac{1}{5}+\frac1{10}+\ldots+\frac1{5n}=\frac{p_n}{5q_n}$. This will be a multiple of 5 if $ p_n$ is not divisible by 5. If, on the other hand, $ p_n$ is a multiple of 5, then $ q_n$ is not, so the 5 will cancel. Corollary IV: If we define $ D$ to be the set of integers such that $ q_n$ is not divisible by 5 and $ N$ to be the set of integers such that $ p_n$ is divisible by 5 then $ N$ is a subset of $ D$ and for $ 0\le k\le 4$ and $ n>0$, $ 5n+k\in D$ iff $ n\in N$. Proof: $ 5n+k\in D$ iff $ n\in N$ is the content of Corollary III. If we let $ n$ be some element of $ N$ that is not in $ D$, then the coprime integers $ p_n$ and $ q_n$ are both divisible by 5, which is a contradiction. Lemma V:$ {1,2,3}\subset (D\setminus N)$, while $ 4\in N\subset D$. Proof:Let us consider the integers 1 to 4 separately: $ \frac11=\frac11$, so 1 is in D but not N $ \frac11+\frac12=\frac32$, so 2 is in D but not N $ \frac11+\frac12+\frac13=\frac{11}6$, so 3 is in D but not N $ \frac11+\frac12+\frac13+\frac14=\frac{25}{12}$, so 4 is in D and in N. Theorem VI: $ N=\{4,20,24\}$, so $ D=\{1,2,3,4,20,21,22,23,24,100,101,102,103,104,120,121,122,123,124\}$ Partial Proof: Since 4 is in $ N$, it follows that the numbers 20 up to 24 are in $ D$. By inspection, 20 and 24 are the numbers in this range in $ N$. Thus the numbers in the ranges $ [100..104]$ and $ [120..124]$ are both contained in $ D$. By further inspection, none of these numbers are in $ N$. Then given a minimal number $ n$ other than $ {4,20,24}$ in $ N$, $ n\ge 5$ by Lemma V. Then $ n=5k+r$ for some positive integer $ k$ and integer $ 0\le r\le 4$. Then $ n$ is in $ N$ which means that $ n$ is in $ D$ and hence $ k$ is in $ N$ by Corollary IV. By the minimality of $ N$, $ k\in\{4,20,24\}$ and hence $ n\in\{21,22,23,100,101,102,103,104,120,121,122,123,124\}$. However, we have already inspected that none of these $ n$ are in $ N$. Luke See my puzzle blog at http://bozzball.blogspot.com