13
$\begingroup$

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?

$\endgroup$
14
  • 5
    $\begingroup$ 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. $\endgroup$
    – Nate
    Apr 2, 2021 at 16:43
  • 4
    $\begingroup$ There's also a Wikipedia article, quoting recent results that improve the bound to $10^{15}$. $\endgroup$ Apr 2, 2021 at 16:50
  • 5
    $\begingroup$ @NN2: Why? It's clearly an integer, so $m=1$ and can therefore be omitted. $\endgroup$
    – Asaf Karagila
    Apr 2, 2021 at 16:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – davidlowryduda
    Apr 2, 2021 at 16:55
  • 4
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila
    Apr 2, 2021 at 16:56

4 Answers 4

28
$\begingroup$

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.

$\endgroup$
3
  • 9
    $\begingroup$ 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}.$$ $\endgroup$ Apr 2, 2021 at 17:45
  • $\begingroup$ @RaviFernando That is an excellent observation. $\endgroup$
    – davidlowryduda
    Apr 2, 2021 at 17:56
  • 1
    $\begingroup$ @davidlowryduda Thank you for this beautiful answer!!! I accepted it! $\endgroup$
    – user318394
    Apr 6, 2021 at 6:32
13
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Omer
    Apr 2, 2021 at 17:12
  • 1
    $\begingroup$ Ah, another with the same proof. It turns out this takes me at least 5 minutes to write out. $\endgroup$
    – davidlowryduda
    Apr 2, 2021 at 17:12
  • $\begingroup$ @davidlowryduda You did take more time doing the careful formatting and elaborating the steps. +1 from me. $\endgroup$
    – Oussema
    Apr 2, 2021 at 17:14
  • $\begingroup$ Some (...) deleted my answer, a vote to undelete would be appreciated. $\endgroup$
    – Igor Rivin
    Apr 2, 2021 at 18:32
  • $\begingroup$ @IgorRivin sorry I don't have enough reputation yet $\endgroup$
    – Oussema
    Apr 2, 2021 at 18:35
7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I upvoted your answer, but you will admit that your computation is a lot more complicated than mine :) $\endgroup$
    – Igor Rivin
    Apr 2, 2021 at 16:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – Aphelli
    Apr 2, 2021 at 17:03
  • $\begingroup$ "What is under the hood"? I can only hope you are joking. $\endgroup$
    – Igor Rivin
    Apr 2, 2021 at 17:05
  • $\begingroup$ @Mindlack I have a similar idea. Please check out my answer. $\endgroup$
    – Oussema
    Apr 2, 2021 at 17:07
  • $\begingroup$ @Igor Rivin: wait, you mean that Mathematica just computes the decimal expansion and checks whether there’s a nonzero digit? $\endgroup$
    – Aphelli
    Apr 2, 2021 at 17:39
0
$\begingroup$

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

$\endgroup$
9
  • 4
    $\begingroup$ I'm not the downvoter. However, Mathematica can be wrong; I have already seen such cases. Moreover, this is not a proof. $\endgroup$ Apr 2, 2021 at 16:43
  • 2
    $\begingroup$ @Ooussema That IS a proof. As for "mathematical can be wrong" - true, but not for arithmetic. $\endgroup$
    – Igor Rivin
    Apr 2, 2021 at 16:44
  • 9
    $\begingroup$ @IgorRivin Not a very insightful proof, however $\endgroup$
    – Some Guy
    Apr 2, 2021 at 16:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – user318394
    Apr 2, 2021 at 16:51
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 2, 2021 at 17:09

You must log in to answer this question.