# Is $\sqrt{2000!+1}$ a rational number?

Is $$\sqrt{2000!+1}$$ a rational number? This may seem trivial, but as I wrote $$2000!+1=n^2$$ for $$n\in\mathbb{N}$$, I realised that it probably is not a rational number and that I cannot build a constructive proof, because $$n^2-1>2^{2000}$$ as from here Prove by induction that $n!>2^n$ and also, as $$n!<(\frac{n+1}{2})^{n}$$ $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction and $$n^2-1<(1001+\frac{1}{2})^{2002}$$ and these are already extremely hard tot tackle. Any help, please?

• According to oeis.org/A146968 the only values of $n$ with $n < 10^9$ such that $n!+1$ is a perfect square are $n=4,5,7$. I think it's reasonable to expect that these are the only such values, but that seems to be open.
– Nate
Apr 2, 2021 at 16:43
• There's also a Wikipedia article, quoting recent results that improve the bound to $10^{15}$. Apr 2, 2021 at 16:50
• @NN2: Why? It's clearly an integer, so $m=1$ and can therefore be omitted. Apr 2, 2021 at 16:53
• This is a purely computational problem, and can be solved purely computationally. The only integers with rational square roots are squares. Then to determine this, it suffices to compute the square root of $2000! + 1$ with enough precision (it seems that 3000 digits is enough, as I just did it on my machine). Or alternately, find the two bounding square numbers that surround $2000! + 1$, which can be done using only big integer arithmetic and a bisection-type algorithm. Apr 2, 2021 at 16:55
• @NN2: Yes, I know what is a rational number. But a rational number is the square of an integer if and only if it is an integer. Apr 2, 2021 at 16:56

Here is a proof that can be done by hand, though certain steps are simplified by having a computer.

1. First, note that $$2003$$ is prime. (You could check this by noting that no primes below $$50$$ divide it).
2. It follows from Wilson's Theorem that $$2002! \equiv -1 \bmod 2003$$. We then also have that $$2000! \equiv -1 \cdot (2002)^{-1} (2001)^{-1} \bmod 2003,$$ and $$2002^{-1} \equiv 2002 \bmod 2003$$ (as this is just $$-1$$). A bit more work, perhaps using the extended Euclidean algorithm, shows that $$2001^{-1} \equiv 1001 \bmod 2003$$. Thus $$2000! \equiv 1001 \bmod 2003.$$
3. We thus have that $$2000! + 1 \equiv 1002 \bmod 2003.$$ If we could show that $$1002$$ is not a square mod $$2003$$ (it's not), then we'll be done. To do this, we can use quadratic reciprocity. Namely we consider the Legendre symbol $$\left( \frac{1002}{2003} \right) = \left( \frac{2}{2003} \right) \left( \frac{3}{2003}\right) \left( \frac{167}{2003} \right). \tag{1}$$
4. As $$2003 \equiv 3 \bmod 8$$, we know that $$2$$ is not a square mod $$2003$$. This is the first symbol.
5. For $$3$$, we use quadratic reprocity. The sequence of steps goes $$\left( \frac{3}{2003} \right) = -\left( \frac{2003}{3} \right) = - \left( \frac{2}{3} \right) = 1.$$ Thus $$3$$ is a square mod $$2003$$.
6. For the last one, the sequence of steps goes $$\left( \frac{167}{2003} \right) = - \left( \frac{2003}{167} \right) = -\left( \frac{166}{167} \right),$$ which we should recognize as asking if $$-1$$ is a square mod $$167$$. As $$167 \equiv 3 \bmod 4$$, it's not a square. Thus $$167$$ is a square mod $$2003$$.
7. We can now conclude. The line in $$(1)$$ evaluates to $$-1 \cdot 1 \cdot 1 = -1,$$ and thus $$2000! + 1$$ is not a square mod $$2003$$. And thus it's not a square.

Ravi Fernando pointed out an observation that gives an enormous simplification in the comments. The observation is that $$1002 \cdot 2 \equiv 2004 \equiv 1 \bmod 2003$$, and thus $$1002 = 2^{-1} \bmod 2003$$. Thus $$1002$$ is a square if and only if $$2$$ is a square (mod $$2003$$). As $$2003 \equiv 3 \bmod 8$$, $$2$$ is not a square, and thus $$1002$$ is not a square.

• You can save a lot of work by noting that $1002 = 2^{-1} \pmod{2003}$, and therefore 1002 is a square if and only if 2 is. A similar idea simplifies step 2 $$2000! \cong -1 \cdot (-1)^{-1} \cdot (-2)^{-1} \cong 2002 \cdot -1 \cdot -1/2 \cong 1001 \pmod{2003}.$$ Apr 2, 2021 at 17:45
• @RaviFernando That is an excellent observation. Apr 2, 2021 at 17:56
• @davidlowryduda Thank you for this beautiful answer!!! I accepted it!
– user318394
Apr 6, 2021 at 6:32

We know that $$2003$$ is prime. So, by Wilson's theorem, $$2002! \equiv -1 \pmod{2003}$$

$$2002 \equiv -1 \pmod{2003}$$.

As such, $$2001! \equiv 1 \pmod{2003}$$

We can use the Euclidean algorithm to get that $$1001 \cdot 2001 \equiv 1 \pmod{2003}$$

As such $$2000! \equiv 1001 \pmod{2003}$$

Which means that $$2000! +1 \equiv 1002 \pmod{2003}$$.

We want to prove that $$1002$$ is not a quadratic residue modulo $$2003$$.

To do that we'll use the law of quadratic reciprocity.

$$\left(\frac{1002}{2003}\right) = \left(\frac{2}{2003}\right) \cdot \left(\frac{3}{2003}\right) \cdot \left(\frac{167}{2003}\right)$$.

$$\left(\frac{2}{2003}\right) = - 1$$ because $$2003 \equiv 3 \pmod8$$

$$\left(\frac{3}{2003}\right) = -\left(\frac{2003}{3}\right) = -\left(\frac{-1}{3}\right) = 1$$ because both $$3$$ and $$2003$$ are congruent to $$3$$ mod $$4$$.

$$\left(\frac{167}{2003}\right) = - \left(\frac{2003}{167}\right) = -\left(\frac{-1}{167}\right) = 1$$ because both $$167$$ and $$2003$$ are congruent to $$3$$ mod $$4$$.

$$\left(\frac{1002}{2003}\right) = -1$$ which means $$2000! + 1$$ is not a perfect square.

• @Quessema That's the idea I had too (I just didn't have time to finish the quadratic reciprocity law computations), another way to find that $1001 \cdot 2001 = 1 (\mod 2003)$ is to note that $2 \cdot 1002 = 1 (\mod 2003)$ and $2001=-2 \rightarrow 1/2001=-1/2 = -1002=1001$.
– Omer
Apr 2, 2021 at 17:12
• Ah, another with the same proof. It turns out this takes me at least 5 minutes to write out. Apr 2, 2021 at 17:12
• @davidlowryduda You did take more time doing the careful formatting and elaborating the steps. +1 from me. Apr 2, 2021 at 17:14
• Some (...) deleted my answer, a vote to undelete would be appreciated. Apr 2, 2021 at 18:32
• @IgorRivin sorry I don't have enough reputation yet Apr 2, 2021 at 18:35

I hope this doesn’t get downvoted but I’ll write it down nonetheless: it can be computed (wolfram did it) that $$2000!+1$$ is congruent to $$371$$ mod $$2017$$ and $$2017$$ is a prime. But $$371^{1008}$$ is $$-1$$ mod $$2017$$ (again, by wolfram), so that $$371$$ is not a square mod $$2017$$, and thus $$2000!+1$$ cannot be a square (and rational square roots of integers are integers, which completes the proof).

• I upvoted your answer, but you will admit that your computation is a lot more complicated than mine :) Apr 2, 2021 at 16:58
• It takes more lines and is far more ad hoc, sure. :) But at least we know exactly what’s under the hood (though I’m now unsure how good that is anyway because no one will reproduce this computation). Apr 2, 2021 at 17:03
• "What is under the hood"? I can only hope you are joking. Apr 2, 2021 at 17:05
• @Mindlack I have a similar idea. Please check out my answer. Apr 2, 2021 at 17:07
• @Igor Rivin: wait, you mean that Mathematica just computes the decimal expansion and checks whether there’s a nonzero digit? Apr 2, 2021 at 17:39

In Mathematica,

IntegerQ[Sqrt[2000!+1]] returns False, so you are good.

ADDENDUM For those who think there should be a cute "human" proof, read https://www.wikiwand.com/en/Brocard%27s_problem

• I'm not the downvoter. However, Mathematica can be wrong; I have already seen such cases. Moreover, this is not a proof. Apr 2, 2021 at 16:43
• @Ooussema That IS a proof. As for "mathematical can be wrong" - true, but not for arithmetic. Apr 2, 2021 at 16:44
• @IgorRivin Not a very insightful proof, however Apr 2, 2021 at 16:46
• @IgorRivin Hi Igor. I didn't downvote your answer. However, it is not a proof. It is rather an observation. A proof would be appreciated! Thank you.
– user318394
Apr 2, 2021 at 16:51
• Also, it's not difficult to write a program for oneself that does enough bignum arithmetic from scratch to verify the claim that $a^2 < 2000!+1 < (a+1)^2$ for some concretely given $a$. It doesn't have to be particularly efficient bignum arithmetic for these sizes -- so just use base 10 -- and finding an $a$ to input into the program can be done with standard software, which we don't need to trust as long as it happens to produce the $a$ that works. Apr 2, 2021 at 17:09