10

This is a "pupil-level" problem from a Chinese software Xiaohongshu (Chinese version Twitter/Reddit/Quora/Insta). Unfortunately, its "official" solution is wrong: The solution states that $m! - n!$ contains a prime factor larger than $m$, however $37! - 35! = 35! \times (36 \times 37 - 1) = 35! \times 11^3$.

I found this problem extremely hard for me. I can only prove partial results:

(1)If $m \geq 2n > 4$, then $m! - n!$ is never a square.

Proof: Let $p$ be the largest prime $\leq n$. According to the Bertrand's postulate, $p > \frac{n}{2}$. Therefore, $v_p(n!) = 1$. Since $m \geq 2n \geq 2p$, $v_p(m!) \geq 2$, therefore $v_p(m!-n!) = 1$, hence $m! - n!$ is not a perfect square.

(2)If $m = n+1$, then $m! - n!$ is never a perfect square.

Proof: $m! - n! = n \times n! = n^2 \times (n-1)!$. However, $(n-1)!$ is never a perfect square when $n \geq 2$ (see here if you are confused). Therefore $(n+1)! - n!$ is not a perfect square for $n \geq 2$.

(3) If $popcount(\lfloor \frac{n}{2} \rfloor)$ is odd, then $m! - n!$ is never a perfect square.

Proof: The case $m = n+1$ has been discussed in (2). For $m > n+1$, by Legendre's formula, $v_2(m) = \sum\limits_{i=1}^\infty \lfloor \frac{m}{2^i} \rfloor > v_2(n)$, however $v_2(n)$ is an odd number, therefore $v_2(m! - n!)$ is also odd.

We note that the parity of $v_2(n)$ equals $popcount(\lfloor \frac{n}{2} \rfloor)$, where popcount means the number of $1$ in a number's binary representation. For example, $popcount(7) = popcount(111_2) = 3$ and $popcount(6) = popcount(110_2) = 2$.

This problem, on the one hand, seems easy. Intuition and Python experiments show the $m! - n!$ are never perfect squares, as it is "somehow difficult" to make $v_p(m! - n!)$ even for every $p$. On the other hand, it is also difficult. When $m > n+1$, it might require analysis on the expression $\Pi_{i=n+1}^m i - 1$, while the term "$-1$" is quite annoying. I am curious whether it is possible to introduce some analytic or algebraic tools?

Muses_China
  • 1,008
  • 5
  • 17
  • 1
    This can probably be strengthened : For positive integers $a<b$ , $b!-a!$ seems only to be a perfect power for $a=2,b=3$. Upto $b=3\ 000$ , there is no further one. – Peter Dec 17 '23 at 15:50
  • 1
    See https://math.stackexchange.com/questions/4819935/factorial-equation-and-no-solution-existing-a-conjecture for analogous problem – Miss and Mister cassoulet char Dec 17 '23 at 17:24
  • 1
    It is known that a finite product of consecutive are never a power (Erdös). So if $m!-n!$ is a square then all prime factor of $n!$ whose exponent is not even should be also a factor of $(n+1)(n+2)\cdots (m-1)m-1$. It seems quite unlikely. – Piquito Dec 17 '23 at 18:52
  • 1
    Note that heuristically this number should be finite (and given the bounds that we have on a smallest example, probably zero): the 'probability' that a randomly chosen number $x$ is square is roughly $\frac1{\sqrt{x}}$, and thus the probability that any of the numbers between $(m+1)!-m!$ and $(2m)!-m!$ are square is bounded from above by $\sum_{k=1}^m\dfrac{1}{\sqrt{(m+k)!-m!}}$ $\leq \sum_{k=1}^m\dfrac1{\sqrt{m!}}=\dfrac {m}{\sqrt{m!}}$, and the last function there decreases superexponentially fast, so the sum over all $m$ is finite. – Steven Stadnicki Dec 17 '23 at 22:49

2 Answers2

1

There may be a very elementary way to prove this, but I don't see it. An old argument of Erdos and Oblath (from a paper in 1937) gives this result with finitely many exceptions. Using bounds for primes in intervals due to Rosser and Schoenfeld, it's not too hard to complete the proof. What Erdos and Oblath do is to split the cases depending on whether or not $$ m > n + \frac{n}{6 \log n} $$ and show that there exists a prime $p$ with $$ \frac{n}{2} < p < \frac{n}{2} + \frac{n}{12 \log n}, $$ for suitably large $n$. If we have $m > n + \frac{n}{6 \log n}$, then this prime $p$ shows up precisely once in $m!-n!$. If $m \leq n + \frac{n}{6 \log n}$, then an easy upper bound upon $m!/n!$ contradicts the fact that every prime in $(n/2,n)$ must divide what you obtain by factoring $n!$ out of $m!-n!$.

Mike Bennett
  • 3,494
-1

We know that $n!$ and $m!$ would never be a perfect square using Bertrand's postulate. For details see this answer

Result 1: In factorisation of $k!$ there will exist atleast one prime number $p_k$ whose power will be $1$, and $p_k \neq k$

Result 2: If in prime factorisation of a number $k$ there exist a prime whose power is odd, then $k$ would never be a perfect square.

Now, $m! - n! = n! (\frac{m!}{n!} - 1)$

By applying Result 1 we can say that in prime factorisation of $n!$ there will exist at least a prime $p_n$ whose power will be $1$.

We know that $m > n$ then $m!$ would contain all prime factors of $n!$ thus prime factorisation of both will contain $p_n$ one time. Thus prime factorisation of $m! - n!$ would contain only one instance of $p_n$.

Since, this $p_n$ exist once as per result 2, $m! - n!$ would not be a perfect square.

As pointed in a comment let me add a case to answer:

Case: $m - n = 1$

In such case: $ m! - n! = n!(m-1) = n!×n = n^2 × (n-1)!$

So, in case of $6! - 5!$, $5^2$ divides $6! - 5!$ is due to nature of the substraction not because 5 is prime.

madhurkant
  • 85
  • 3
    This doesn't quite work. For example, $5!$ and $6!$ each have exactly one $5$ in their prime factorisation, but $6!-5!$ is divisible by $5^2$. – Especially Lime Dec 19 '23 at 08:22
  • @EspeciallyLime Earlier I drafted answer on a case basis. It contained a special case of $m-n = 1$. And your case perfectly is inline with it. The fact that $6! - 5!$ is divisible by $5^2$ is due to the fact that $6 - 5 = 1$. You can check by yourself that $104! - 103!$ or for any case where $m-n = 1$. This is due to special case of answer. – madhurkant Dec 19 '23 at 09:21
  • 1
    But also $8!-5!$ is divisible by $5^2$. – Especially Lime Dec 19 '23 at 09:31
  • I cannot get the point you are trying to convey. Mention explicitly, what you want to convey by these divisions? @EspeciallyLime – madhurkant Dec 19 '23 at 09:45
  • Seems you are confused, i have said in answer 'will exist at least a prime' didn't said only one prime. In $5!$ There is also exactly one power of $3$ and, see, $8! - 5!$ is not divisible by $3^2$. – madhurkant Dec 19 '23 at 09:58
  • 1
    Well how on earth do you know that there is a prime that divides $m!-n!$ exactly once? Your answer seems to be claiming that any prime dividing $n!$ exactly once works, which is not true, and is still not true even when you require $m\neq n+1$. – Especially Lime Dec 19 '23 at 10:59
  • A fair effort, but not a proof and thus not an answer, and so I had to downvote, as it should be deleted. -1 – Mike Dec 21 '23 at 17:55
  • @Mike no problem. – madhurkant Dec 22 '23 at 09:52