26
$\begingroup$

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.

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

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – S.C.B. Feb 15 '16 at 2:37
  • $\begingroup$ I don't know (+ a few characters to reach to minimum comment length) $\endgroup$ – Julian Rosen Feb 15 '16 at 2:45

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.