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$ 144 Answers
$\begingroup$Here is a proof that can be done by hand, though certain steps are simplified by having a computer.
- First, note that $2003$ is prime. (You could check this by noting that no primes below $50$ divide it).
- 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.$$
- 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}$$
- As $2003 \equiv 3 \bmod 8$, we know that $2$ is not a square mod $2003$. This is the first symbol.
- 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$.
- 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$.
- 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 $\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 $\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$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
$\endgroup$ 9
