About summation with p-adic valuation

Question

Here is a problem i came across. Prove that $$\sum_{i=1}^{n}\frac{1}{i}$$ is not an integer for $n \geq 2$. The book olympiad number theory by Justin Stevens says that after writing $\frac{1}{i}$ as $\frac{\frac{n!}{i}}{n!}$, we need to proceed with $p-$adic valuation. He consider $v_2(\frac{n!}{i})$ and somehow gets an equality $v_2(\sum_{i=1}^{n}\frac{n!}{i})=v_2(\frac{n!}{2^{\lfloor log_2n \rfloor}})$. I tried many times but cannot understand how it happened. Please sirs can you explain me?

Answer 1

What happened there? Recall how the triangle inequality* works in the $p$-adic valuation: $v_p(x+y)\ge\min(v_p(x),v_p(y))$. So then, if $2^k$ is the largest power of $2$ less than or equal to $n$, $$v_2\left(\sum_{i\le n, 2^k\nmid i} \frac{n!}{i}\right) \ge \max_{i\le n, 2^k\nmid i} v_2\left(\frac{n!}{i}\right) = v_2\left(\frac{n!}{2^{k-1}}\right)$$ There is exactly one term for which $2^k$ divides $i$; $i=2^k$ itself. Now, if $v_p(x)<v_p(y)$, $v_p(x)\ge\min(v_p(-y),v_p(x+y))$. The only way for both inequalities to be true is if $v_p(x+y)\le v_p(x)$; combined with the standard form of the triangle inequality, $v_p(x+y)=v_p(x)$ if $v_p(x)<v_p(y)$. Consequently, $$v_2\left(\sum_{i\le n} \frac{n!}{i}\right) = v_2\left(\frac{n!}{2^k}+\sum_{i\le n, 2^k\nmid i} \frac{n!}{i}\right) = v_2\left(\frac{n!}{2^k}\right)=v_2(n!)-k$$ And that's what we needed. If $\sum_{i\le n}\frac1i$ were an integer, $v_2\left(\sum_{i\le n}\frac{n!}{i}\right)$ would be $\ge v_2(n!)$. It's not, so we have that the sum is not an integer, for any $n\ge 2$.

(*) How is this a triangle inequality? The function $|x|_p=p^{-v_p(x)}$ is an actual distance function, and this is how the strong triangle inequality $|x+y|_p\le\max(|x|_p,|y|_p)$ translates to valuation terms.

Answer 2

$v_2(m)$ is the number of times $2$ divides $m$. This means that $v_2(m)$ is the number $k$ such that $m\equiv0\pmod {2^k}$ but $m\not\equiv0\pmod {2^{k+1}}$

If we have a finite sum $A=a_1+\cdots+a_s$ of integers with $v_2(a_1)<v_2(a_j)$ for all $j>1$ then $v_2(A)=v_2(a_1)$. This is because $a_1+\cdots+a_s \equiv0\pmod{2^k}$ for $k=v_2(a_1)$ but $a_1\not\equiv0\pmod{2^{k+1}}$ and $a_2+\cdots+a_s\equiv0\pmod{2^{k+1}}$ so that $A\not\equiv0\pmod{2^{k+1}}$.

Now consider the sum $n!/1+n!/2+\cdots+n!/n$. Take $2^i$ to be the greatest power of $2$ which is $\le i$. Then $v_2(j)<v_2(2^i)$ for all $j\in\{1,\ldots, n\}$ except $j=2^i$. Therefore $v_2(n!/j)>v_2(n!/2^i)$ for all $j\in\{1,\ldots, n\}$ except $j=2^i$. (Of course all the $n!/j$ are integers.) Therefore $$v_2(n!/1+n!/2+\cdots+n!/n)=v_2(n!/2^i)=v_2(n!)-i<v_2(n!)$$ as long as $n\ge2$. Thus $n!$ cannot divide the integer $n!/1+n!/2+\cdots+n!/n$, equivalently $1/1+1/2+\cdots+1/n$ isn't an integer.