# Numbers that are clearly NOT a Square

Although I have never studied math very seriously, I have heard of Brocard's Problem, which asks for integer solutions for the following Diophantine Equation:$$n!+1=m^2$$

The only solutions are conjectured to be $(4,5),(5,11),(7,71)$, and there are no solutions for $n < 10^{9}$.

However, it is clear there are an infinite amount of $n$ where it is simple to verify $n!+1$ is not a square.

For example, take $n=81$. Assume that $81!+1$ is a square.

This implies that $81!-1=a^2-2$ for some integer $a$.

Note that by Wilson's Theorem, $82!\equiv -1 \pmod {83}$, implying $81! \equiv 1 \pmod {83}$.

Thus, $a^2-2 \equiv 0 \pmod {83}$. A contradiction, since $2$ is not a quadratic residue of $83$.

In a similar way, we can claim that for all $n>5$ where $n+2$ is a prime number $p$ such that $p \equiv 3,5 \pmod 8$, then $n!+1$ is not a square.

My question is, are there any other integers $n$ where it is simple to verify $n!+1$ is not a square? Any help would be appreciated.

• @barakmanos Thanks! I appreciate that you like my question. – S.C.B. Feb 14 '16 at 8:22

Your nice argument can be generalized.

For example, take $n=80$. You deduced from Wilson's Theorem that $81!\equiv 1\pmod {83}$. Now $$80!\equiv \frac{1}{81}\equiv -\frac{1}{2}\pmod{83}.$$ Here $\frac{1}{2}$ means the inverse of $2$ modulo $83$. It follows that $80!+1\equiv -\frac{1}{2}+1=\frac{1}{2}\pmod{ 83}$. Because $2$ is not a quadratic residue modulo $83$, neither is its inverse, so $80!+1$ cannot be a square. Of course, this works for any $n$ for which $n+3$ is prime congruent to $3$ or $5$ modulo $8$.

More generally, for any prime $p$ and positive integer $k\leq p-1$, $$(p-k)!+1\equiv \frac{(-1)^k}{(k-1)!}+1=\frac{(k-1)! \big[(k-1)!+(-1)^k\big]}{((k-1)!)^2}\mod p.$$ So $(p-k)!+1$ is a quadratic residue modulo $p$ if and only if $(k-1)! \big[(k-1)!+(-1)^k\big]$ is a quadratic residue. Via quadratic reciprocity this can be translated to a condition on $p$.

For each $k\geq 1$, there is a condition similar to yours. I'll list the first three (they start looking complicated very fast). The quantity $n!+1$ cannot be a square if any of the following conditions hold:

• $n+2$ is a prime congruent to $3$ or $5$ mod $8$
• $n+3$ is a prime congruent to $3$ or $5$ mod $8$
• $n+4$ is a prime congruent to $5$, $9$, $21$, $23$, $31$, $37$, $43$, $45$, $49$, $51$, $55$, $57$, $59$, $65$, $67$, $69$, $71$, $73$, $77$, $81$, $83$, $85$, $87$, $91$, $95$, $97$, $99$, $101$, $103$, $109$, $111$, $113$, $117$, $119$, $123$, $125$, $131$, $137$, $145$, $147$, $159$, or $163$ mod $168$.

The primes in the third case are exactly those for which $42$ is a quadratic non-residue.

• Nice. Was this known/discussed before? When I first thought of this I wondered if this could make testing if $n!+1$ is a square easier, but seems to be that that seems difficult. – S.C.B. Feb 15 '16 at 2:37
• I don't know (+ a few characters to reach to minimum comment length) – Julian Rosen Feb 15 '16 at 2:45