1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$) ? $\endgroup$ – coffeemath Mar 20 '19 at 4:36
  • $\begingroup$ I don't see the $v_2$ equation either... but upvoted question. I'd like to see that, hope someone gives a solution. $\endgroup$ – coffeemath Mar 20 '19 at 4:52
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can you suggest me a book on p-adics sir? I am not so familar with it $\endgroup$ – user655794 Mar 20 '19 at 5:14
  • $\begingroup$ You have a typo.... $v_p(x+y)=v_p(x)$ if $v_p(x) \leq v_p(y)$. $\endgroup$ – user655794 Mar 20 '19 at 5:30
  • $\begingroup$ 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. $\endgroup$ – jmerry Mar 20 '19 at 5:33
  • $\begingroup$ Oh yes sorry i mistakely used \leq :( $\endgroup$ – user655794 Mar 20 '19 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy