# About summation with p-adic valuation

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?

• Looks like one took $\frac{1}{i!}$ and multiplied top by $n!$ while dividing bottom by $n!.$ How is that the same (unless $n!=1$) ? – coffeemath Mar 20 '19 at 4:36
• I don't see the $v_2$ equation either... but upvoted question. I'd like to see that, hope someone gives a solution. – coffeemath Mar 20 '19 at 4:52

## 2 Answers

$$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) 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) 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 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.

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(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). 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.

• Can you suggest me a book on p-adics sir? I am not so familar with it – user655794 Mar 20 '19 at 5:14
• You have a typo.... $v_p(x+y)=v_p(x)$ if $v_p(x) \leq v_p(y)$. – user655794 Mar 20 '19 at 5:30
• No book suggestions; I didn't learn this from a book myself. Also, mistake corrected. It was more an editing mistake than a typo - I started out using the negative of the valuation, and missed one spot when I reversed the signs. Your attempted correction is wrong; that needs to be a strict inequality. – jmerry Mar 20 '19 at 5:33
• Oh yes sorry i mistakely used \leq :( – user655794 Mar 20 '19 at 5:38