wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> 4n + 1 divides 1 + 4(n!)^4
        
(Message started by: THUDandBLUNDER on Feb 25^th, 2005, 4:05am)

Title: 4n + 1 divides 1 + 4(n!)^4
Post by THUDandBLUNDER on Feb 25^th, 2005, 4:05am

Let n be an integer such that 4n + 1 divides 1 + 4(n!)⁴
Prove that n is a perfect square.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Eigenray on Mar 18^th, 2005, 12:34pm

Well, I have something, at least:
Suppose 4n+1 | 4(n!)⁴+1.
If p | 4n+1, then we must have p > n, otherwise p | n!.
If 4n+1 weren't prime, we'd therefore have 4n+1 >= (n+1)², which only holds for n<=2, and those cases are easily checked.
Thus p=4n+1 is prime, and is therefore uniquely (up to sign and order) the sum of two squares, p=a²+b²; we therefore want a²=1, b²=4n.

Note that 1+4r⁴ = (1+2r+2r²)(1-2r+2r²) = (r²+(r+1)²)(r²+(r-1)²),
and moreover that the two factors are relatively prime, since (1+2r+2r²,4r)=1.
Thus we have
p | (n!)² + (n! +- 1)²,
and since n! is relatively prime to p,
(1 +- 1/n!)² = -1 = (2n)!² mod p,
and it follows
n! +- 1 = +- (2n)!n! mod p.
Then I run out of ideas. One also has
(2n!²)² = -1 = (2n)!² mod p,
so 2n!² = +- (2n)!, i.e., (2n Choose n) = +- 2 mod p.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by THUDandBLUNDER on Mar 19^th, 2005, 7:23am

Quote:

Thus p=4n+1 is prime, and is therefore uniquely (up to sign and order) the sum of two squares, p=a²+b²; we therefore want a²=1, b²=4n.

According to Davenport, there is a result due to Gauss that
a prime p = 4n + 1 equals a² + b² where a = (2n)! / [2(n!)²] (mod p)
Hope this helps.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Eigenray on Mar 19^th, 2005, 11:17am

on 03/19/05 at 07:23:56, THUDandBLUNDER wrote:

According to Davenport, there is a result due to Gauss that
a prime p = 4n + 1 equals a² + b² where a = (2n)!/[2(n!)²] (mod p)
Hope this helps.

Well, that'll do it: a=+-1 mod p implies a=+-1, so b²=p-a²=4n, and n is square.

Do you have a reference for that? I'm only aware of non-constructive proofs that p is the sum of two squares. It doesn't seem to be in Hardy&Wright or Niven either.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by THUDandBLUNDER on Mar 19^th, 2005, 12:55pm

I was afraid you would ask that.
No, I don't have the Davenport reference but I might be able to find it.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Eigenray on Mar 19^th, 2005, 2:29pm

My friend has a copy of Davenport's "The Higher Arithmetic". Section V.3 states:

The second construction is that of Gauss [1825], and this is the most elementary of all to state, though not to prove. If p=4k+1, take
x = (2k)!/(2 k!²) (mod p), y= (2k)!x (mod p),
with x and y numerically less than p/2. Then p=x²+y². A proof was given by Cauchy, and another by Jacobsthal, but neither of these is very simple.

He refers to Dickson's History of the Theory of Numbers, vol II ch 6, and vol III ch 2.

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Barukh on Mar 20^th, 2005, 12:26am

Here (http://groups-beta.google.com/group/sci.math/msg/286bb781c140dcd3) is something resembling the argument for Gauss's statement, but it is too cryptic for me to comprehend.

Maybe, somebody else?

Besides, a very beautiful problem!

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Deedlit on Mar 31^st, 2005, 6:11am

Well, characters are just maps from groups to the multiplicative complex plane with certain properties.

Quote:

If chi:F_p^* -> C^* is a character of degree 4, then
t = sum_{c=2}^{p-1} chi(c)chi(1-c)
is a Gaussian integer r + s i with r^2 + s^2 = p.

OK. Note that degree 4 means that the range is {1,i,-1,-i}. It looks like it has to be onto as well.

Quote:

Now consider congruences in Z[i] modulo t.

Observe that t generates a lattice with cells of area p. Each imaginary value will have elements of (t), spaced p spaces apart.

Quote:

A priori
either chi(c) = c^n (mod t) for all c or
chi(c) = c^{3n} (mod t) for all c (I forget which but never mind).

I don't know why he says "a priori" - it's certainly not "a priori" to me! It looks like chi(c) = c^{3n} (mod t) is the correct version.

Quote:

Then 2r = t + complexconjugate(t)
= sum chi(c)chi(1-c) + sum chi(c)^3chi(1-c)^3
= sum_c c^n(1-c)^n + sum c^{3n} (1-c)^{3n} (mod t).

Sure.

Quote:

Considering this tast modulo p, when we expand out by the binomial
theorem only the term (3n choose n) c^{3n}(-c)^n survives.
The rest is straightforward.

Well, it's no longer character theory, but it's stopped making sense to me. I don't see either how to cancel all the terms, or to get the values of a and b from there.

I'm also not sure why (2n)!² = -1 (mod p). Something simple, I'm sure...

Title: Re: 4n + 1 divides 1 + 4(n!)^4
Post by Barukh on Apr 2^nd, 2005, 4:45am

on 03/31/05 at 06:11:51, Deedlit wrote:

I'm also not sure why (2n)!² = -1 (mod p). Something simple, I'm sure...

Here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1078017611;start=0#6) is a simple demonstration.