15
$\begingroup$

In Dabrowski's paper, he showed that it would follow from the abc conjecture that the equation $$n!+k=m^2$$ has a finite number of solutions $n, m$ for any given $k$ which was my motivation to find solutions for different values of $k$.

Using PARI/GP, I observed that for any $k \gt 1$, if $n!+k$ is a square, then $n \le k$. I didn't find any counterexample in my search that covered a range of $k\le 2500$ and $n\le 10^4$ for each $k$.


Questions:

$(1)$ Can we prove that for any $k \gt 1$, if $n!+k$ is a square then $n \le k$, thereby restricting Dabrowski's original statement?

$(2)$ If false then what would be the smallest counterexample?

Update 1: This also seems true for $n!-k$, when $k\gt 2$.

Update 2: After some more testing on PARI, I conjecture that for any $k \gt 3$, if $n!+k$ is a perfect power, then $n\le k$. This also seems true for $n!-k$.

$\endgroup$
4
  • $\begingroup$ aka $m^2-n!=k$ so $m$ is greater than $\lfloor {n\over 2}\rfloor !$ $\endgroup$
    – user645636
    Jan 6, 2020 at 20:18
  • $\begingroup$ Your observation is true, but it's an easy exercise. $\endgroup$
    – jijijojo
    Jan 6, 2020 at 20:24
  • $\begingroup$ @pigeon I agree, but I couldn't find any other literature on the matter which is why I decided to ask it over here $\endgroup$
    – Mathphile
    Jan 6, 2020 at 20:26
  • $\begingroup$ Heuristically, it's very likely to be true. If $k < n$, that means there is a square between $n!$ and $n! + n$. But for numbers of this size, squares are approximately a distance $\sqrt{n!}$ apart, so heuristically the probability of that happening is very low. $\endgroup$ Jan 6, 2020 at 20:27

2 Answers 2

10
+100
$\begingroup$

Claim: If $k$ is prime and $n!+k$ is a square, then $n \le k$.

Proof: Clearly $k$ can't be $2$ (mod $4$ considerations), so $k$ is odd and then, by mod $4$ considerations, is $1$ mod $4$. Then $n!+k = m^2$ implies that for each odd $p \le n$, $(\frac{k}{p}) = 1$, which implies $(\frac{p}{k}) = 1$ by quadratic reciprocity (since $k$ is $1$ mod $4$). Also, $n!+k = m^2$ directly implies $k$ is $1$ mod $8$, so $(\frac{2}{k}) = 1$. Therefore, if $n \ge k$, then each $p \le k$ has $(\frac{p}{k}) = 1$, and thus by multiplicativity, we get $(\frac{m}{k}) = 1$ for each $m \le k$, which is impossible, since there are $\frac{k+1}{2}$ quadratic residues mod $k$. $\square$

.

WE Tutorial School's answer below shows that $n \le k$ if $k$ is a nonsquare composite. The argument is as follows. Note $k \mid \frac{n!}{k}$, since if $k = rs$ for $1 < r < s < k$, then $r,s$ appear in $n!$ as well as $k$ (assuming $n > k$). So $\frac{n!}{k}+1$ is relatively prime to $k$, but then that $k(\frac{n!}{k}+1) = n!+k$ is a perfect square means that $k$ must be a perfect square, which we assumed it isn't.

.

This leaves open the case of $k$ a perfect square. It should be noted that answering question (1) in the affirmative would then improve Dabrowski's result, so seems hard.

$\endgroup$
2
  • $\begingroup$ OK, on rereading I missed the assumption that $n$ is odd in the post linked. My proof fails when $k+1$ is even as you highlighted. $\endgroup$
    – TheSimpliFire
    Jan 19, 2020 at 9:59
  • $\begingroup$ @TheSimpliFire oh, I didn't know it is true if $k+1$ is odd. thanks for letting me know $\endgroup$ Jan 19, 2020 at 10:06
5
$\begingroup$

In addition to mathworker21's work, we have this claim: if $k$ is a non-square composite number such that $n!+k$ is a perfect square for some positive integer $n$, then $n\le k$. We are left with the case where $k$ is a perfect square.

Since $k$ is a composite number which is non-square, $k=rs$ for some integers $r$ and $s$ such that $1<r<s<k$. If $1<k<n$, then $$n!+k=k\left(\frac{n!}{k}+1\right)=k\ell,$$ where $$\ell=\frac{n!}{k}+1=k\left(\frac{n!}{rsk}\right)+1=k\,(r-1)!\left(\frac{(s-1)!}{r!}\right)\left(\frac{(k-1)!}{s!}\right)\left(\frac{n!}{k!}\right)+1$$ is clearly an integer coprime to $k$. However, as $k\ell$ is a perfect square with $\gcd(k,\ell)=1$, it follows that both $k$ and $\ell$ are perfect square, but this contradicts the assumption that $k$ is non-square.

If $1<k<n$ and $k=t^2$ for some positive integer $t>1$, then we need to show that $$\ell=\frac{n!}{k}+1=\frac{n!}{t^2}+1$$ is not a perfect square. Equivalently, we need to show that $\frac{n!}{t^2}+1$ is never a perfect square of an integer for any positive integer $t$ such that $1<t<\sqrt{n}$. I am not sure how to do that, but it can be easily seen that for $\ell$ to be a perfect square, $n>16$ so that $t,2t,3t,4t< n$, and $$\ell = t^2\left(24\ (t-1)!\ \frac{(2t-1)!}{t!}\ \frac{(3t-1)!}{(2t)!}\ \frac{(4t-1)!}{(3t)!}\ \frac{n!}{(4t)!}\right)+1.$$ I am not quite sure what to do with that.

However, as for when $n!+1$ is a perfect square, this is known as Brocard's problem. So far, the only known values of $n$ that work are $n\in\{4,5,7\}$.


Let $n$ and $k$ be non-negative integers such that $n!-k$ is a perfect square. We want to show that either $(n,k)\in\big\{(0,0),(1,0),(0,1),(1,1),(2,1),(2,2),(3,2)\big\}$ or $k\ge n$.

One can see that $n!$ is a perfect square if and only if $n=0$ or $n=1$. One can see that $n!-1$ is a perfect square if and only if $n=0$, $n=1$, or $n=2$. One can easily see that $n!-2$ is a perfect square if and only if $n=2$ or $n=3$. We assume from now on that $k>2$. Suppose for the sake of contradiction that $k<n$.

We can use the same reasoning as my work above to establish that $k$ cannot be a non-square composite number. However, it is also easily seen that $n\geq 6$. Hence, if $k$ is a perfect square, then $$\frac{n!-k}{k}=\frac{n!}{k}-1\equiv -1\pmod{4}$$ so $\frac{n!-k}{k}$ can never be a perfect square. Hence, in this situation, we are left with the case where $k$ is prime. However, mathworker21's argument can be used again (all credits go to him, so I am making this post a community wiki post).

Suppose now that $k$ is an odd prime. Using the same argument, $-k$ is a quadratic residue modulo $p$ for every odd prime natural number $p\leq n$. By quadratic reciprocity, if $p<k$, then $$\left(\frac{p}{k}\right)\left(\frac{k}{p}\right)=(-1)^{\frac{(k-1)(p-1)}{4}}.$$ As $k\equiv -1\pmod{8}$, we conclude that $$(-1)^{\frac{(k-1)(p-1)}{4}}=(-1)^{\frac{(p-1)}{2}}=\left(\frac{-1}{p}\right).$$ That is, $$\left(\frac{p}{k}\right)=\left(\frac{k}{p}\right)\left(\frac{-1}{p}\right)=\left(\frac{-k}{p}\right)=1.$$ Finally, $$\left(\frac{2}{k}\right)=(-1)^{\frac{k^2-1}{8}}=1.$$ Therefore, every positive integer less than $k$ is a quadratic residue modulo $k$, and this is a contradiction.

$\endgroup$
13
  • 1
    $\begingroup$ +1 yup this pretty much sums everything up. Another user Haran was also able to prove that $n\gt k$ only possible if $k$ is a square, but despite his best efforts he wasn't able to prove the square $k$ case as according to him it became quite similar to Brocard's problem. If you would like to discuss this problem with me and him you can join this chatroom chat.stackexchange.com/rooms/82585/thesimplifires-chatroom $\endgroup$
    – Mathphile
    Jan 11, 2020 at 12:02
  • $\begingroup$ +1 nice argument. I hope you don't mind me adding it to my answer to summarize the progress (with credit given to you), and for increased brevity. $\endgroup$ Jan 11, 2020 at 12:12
  • $\begingroup$ @mathworker21 Oh, I don't mind. Go ahead. $\endgroup$ Jan 11, 2020 at 12:13
  • 1
    $\begingroup$ @mathworker21 It's ok. I am curious what this "community wiki" button does anyway. I have seen this on other people's answers, so I wanted to try it myself. Plus, I solved the problem with $n!-k$ mainly because of your argument. $\endgroup$ Jan 11, 2020 at 12:25
  • 1
    $\begingroup$ In quadratic reciprocity, the power of $-1$ should be divided by $4$ (as opposed to $2$). $\endgroup$
    – TheSimpliFire
    Jan 11, 2020 at 19:38

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.