Many thanks for several replies. This one seems to contain the definitive answer. R. On Tue, 4 Jul 2006, moree@mpim-bonn.mpg.de wrote:
Richard Guy asked:
Presumably 0! = 1! = 0^2 + 1^2. 2! = 1^2 + 1^2 6! = 12^2 + 24^2
are the only integer solutions of
n! = x^2 + y^2
but is there a proof? R.
David Wilson wrote:
No, I don't have a proof, I do have an argument following from a solid conjecture.
We know that for n >= 2, there exists a prime p with n < p < 2n. It also appears that for n >= 4, there exists prime p == 3 (mod 4) with n < p < 2n. I cannot prove this myself, but I am sure it is true.
This conjecture implies that for n >= 7, there is a prime p == 3 (mod 4) with [n/2] < p <= n. This p occurs with exponent 1 in the prime factorization of n, so that n! cannot be of the form x^2+y^2.
***** Paul Erdos seems to have been the first to have supplied such a proof. He namely proved that for n >= 4, there exists a prime p == 3 (mod 4) with n < p < 2n. `Bertrand's Postulate for arithmetic progressions'. The rest of the argument is then as David Wilson described above.
Reference: P. Erdos, Ueber die Primzahlen gewisser arithmetischer Reihen, Math. Zeitschrift 39 (1935), 473-491.
I quote now from p. 491: Mit Hilfe der Primzahltabellen bestimmt man nun leicht die genauen unteren Grenzen von \xi, von welchen ab zwischen \xi (exkl.) und 2\xi (inkl.) Primzahlen von den betrachten Formen existieren. Man findet dass das Intervall \xi < p \le 2\xi fuer \xi \ge 3.5 eine Primzahl von der Form 6k+1, fuer \xi \ge 5.5 eine Primzahl von der Form 6k+5, fuer \zi\ge 6.5 eine Primzahl von der Form 4k+1 und endlich fuer \zi \ge 3.5 eine Primzahl van der Form 4k+3 enthalt. Aus der letzten Tatsache folgt auf Grund eines bekannten Satzen der elementaren Zahlentheorie, dasz 1!, 2! und 6! die einzigen Faktoriellen sind, die sich in die Summe zweier Quadratzahlen zerlegen lassen.
The above article of Erdos gives an elementary method to determine for a certain finite set of moduli d, explicitly numbers x_0(d) and z(d) such that every interval of the form (x,z(d)x) with x>=x_0(d) contains a prime p with p=a(mod d), for any a coprime to d.
More precisely, for a modulus d>=2 put sigma(d)=\sum_{p<d, p does not divide d}1/p, where p runs over the primes. Erdos proved that if sigma(d)<1 and z>d(d-1)^{-1}(1-sigma(d))^{-1}, then there is at least one prime from each primitive congruence class modulo d in the interval (x,zx] for all x sufficiently large. This result can be made effective. Erdos did this for d=4 and d=6 (with the outcome given in the quote above). In my paper
P. Moree, Bertrand's postulate for primes in arithmetical progressions. Comput. Math. Appl. 26 (1993), no. 5, 35--43.
this is done for the remaining 52 values of d satisfying \sigma(d)<1.
Finally, I liked to note that R. Breusch earlier than Erdos published a proof of Bertrands' Postulate for modulus 4. It is rather technical and computational and uses results on the first zeros of L(s,\chi_4).
R. Breusch, Zur Verallgemeinerung des Bertrandschen Postulates, dass zwischen x und 2x stets Primzahlen liegen, Math. Zeitschrift 34 (1932), 505-526.
In the early 30's also G. Ricci worked on Bertrand's Postulate for arithmetical progressions, but I cannot comment on this paper (which I have never seen):
G. Ricci, Sui teorem di Dirichlet relativo alla progressione arithmetica, Bolletino della Unione Mathematica Italiana 12 (1933), 304-309.
I hope this helps, Pieter Moree