Re: Does any "n" exist, such that ( n! + prime(n) ) yields integral square ?‏

[David Harden]

>I extended calculations to n<= 30,000 and still no result. On >Sun, Aug 10, 2008 at 10:01 AM, Alexander >Povolotsky<apovolot at gmail.com
> wrote:
> Hi,
>> Does any "n" exist, such that ( n! + prime(n) ) yields >>integral square ? I tried up to n=3000 to no avail (but my >>be my PARI program is faulty ;-) ) .

It is trivial to check this for n<=3. So we may assume that n >= 4, which means n! is a multiple of 8 and that p_n is odd. 
Then n! + p_n = x^2 means p_n == x^2 (mod 8).
Since p_n is odd, x^2 is odd and, therefore, x^2 == 1 (mod 8) so p_n == 1 (mod 8).

Let q be an odd prime with q <= n. (Note that q < p_n.) Then p_n == x^2 (mod q) so (using Legendre symbol notation)(p_n/q) = 1. Since p_n == 1 (mod 4), quadratic reciprocity tells us that (q/p_n) = 1. Also, (2/p_n) = 1 because p_n == 1 (mod 8).
This means that the smallest prime quadratic nonresidue (equivalently, the smallest positive quadratic nonresidue) modulo p_n  is > n ~ p_n/(log(p_n) - 1). This is very large; known effective bounds on the smallest quadratic nonresidue modulo a prime fall well under this. You have probably searched up to n large enough for these bounds to apply and conclude the proof.

---- David