3
$\begingroup$

How to disprove that $$n! \mid \left(n! + \frac{n!}{2} + \dots + \frac{n!}{n} \right)$$ This should not be true, since it would imply that there is some $n$ such that the $n$-th partial sum of the harmonic series reaches an integer.

Here is what I tried:

Since $n > 2 $ (Otherwise this would me trivial), then: $$ 2 \mid n! \\ 2 \mid \frac{n!}{2} $$ So that $n > 4 $ (Note that $n$ can't be $4$). Then, by the same reasoning: $$ 4 \mid n! \\ 4 \mid \frac{n!}{4} $$ So that $n > 6 $ But then I get stuck here since $ 6 \mid \frac{n!}{6} $ doesn't necessaily make $n$ larger than 6.

$\endgroup$
  • $\begingroup$ Can you prove that $H_n\notin\mathbb{N}$? $\endgroup$ – Michael McGovern Jan 25 '18 at 1:08
  • $\begingroup$ That would of course prove my question! But I would like to see if my attempt to prove that no harmonic number is an integer, has a future. $\endgroup$ – I.Padilla Jan 25 '18 at 1:08
  • $\begingroup$ Brief sketch: If $2^k\le n<2^{k+1}$ then $2^k(1+\cdots+1/n)\equiv1\bmod 2$. $\endgroup$ – anon Jan 25 '18 at 1:11
  • $\begingroup$ How about $\gcd(m,n)=m\rightarrow{n}\ndiv{m}$? $\endgroup$ – Michael McGovern Jan 25 '18 at 1:11
4
$\begingroup$

Let $p$ be the largest prime less than $n$. Then $$ \sum_{i = 1}^n \frac{n!}{i} \equiv \frac{n!}{p} \not\equiv 0\mod p $$ Since $n! \equiv 0\mod p$, it cannot divide that sum.

EDIT: The comments tell me I should explain why $i = 2p$ doesn't appear in the sum. Bertrand's postulate says there is a prime $q$ with $p < q < 2p$. Since $p$ is the largest prime less than $n$, we must have $n < q < 2p$.

$\endgroup$
  • 2
    $\begingroup$ How did you get away without invoking Bertrand's postulate? $\endgroup$ – user491874 Jan 25 '18 at 1:20
  • 1
    $\begingroup$ I just noticed that, in order for this $\frac{n!}{p} \equiv 0 \text{mod $p$}$ to be a contradiction, we would need BP! $\endgroup$ – I.Padilla Jan 25 '18 at 1:25
  • $\begingroup$ @user8734617 Padilla, is right how do you know the power of $p$ in $n!$ is not higher than $1$ if not for Bertrand's postulate? $\endgroup$ – clark Jan 25 '18 at 1:52
  • $\begingroup$ @user8734617 I may have assumed that was obvious. Perhaps I should have mentioned it. $\endgroup$ – eyeballfrog Jan 25 '18 at 2:09
  • $\begingroup$ Yep, would be good IMHO, because "obvious for you" and "obvious for the OP" are two different things. $\endgroup$ – user491874 Jan 25 '18 at 2:18
2
$\begingroup$

For $n\gt 1$ Betrand's postulate shows there is at least one prime $p$ greater than $\frac{n}{2}$ and less than or equal to $n$

So $\left(n! + \frac{n!}{2} + \dots + \frac{n!}{n} \right)$ is the sum of $(n-1)$ multiples of $p$ and one non-multiple of $p$, so is not a multiple of $p$

But $n!$ is a multiple of $p$ so does not divide the sum

$\endgroup$
2
$\begingroup$

Here is a nice proof I gave on my own, of the fact that $H_n$ is not an integer for any $n$. Let $p$ be the greatest prime not exceeding $n$. Now, if you calculate $1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$ by long division, the denominator will be $n!$ and the numerator should be a sum of terms like $\frac{n!}{i}$, where $i$ runs from $1$ to $n$, i.e. $$H_n = \frac{\frac{n!}{1}+\frac{n!}{2}+...+\frac{n!}{n}}{n!}~.$$ Now, the denominator is divisible by $p$. In the numerator, all terms other than $\frac{n!}{p}$ are divisible by $p$, and $\frac{n!}{p}$ is of course not divisible by $p$. Hence, the numerator is not divisible by $p$. This proves that $H_n$ is not an integer.

Note: The proof is slightly incomplete. Can you point out where?

$\endgroup$
  • $\begingroup$ Yep, at the point where you claim that the only term not divisible by $p$ is $\frac{n!}{p}$. If (contrary to Bertrand's postulate) there were no bigger primes between $p$ and $2p$, and if it happened that $2p\le n$, then you would have another term $\frac{n!}{2p}$ not divisible by $p$. $\endgroup$ – user491874 Jan 25 '18 at 1:19
  • $\begingroup$ Yes, you are correct! $\endgroup$ – Usermath Jan 25 '18 at 1:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.