Author |
Topic: 4n + 1 divides 1 + 4(n!)^4 (Read 1612 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
4n + 1 divides 1 + 4(n!)^4
« on: Feb 25th, 2005, 4:05am » |
 Quote  Modify
|
Let n be an integer such that 4n + 1 divides 1 + 4(n!)4
Prove that n is a perfect square.
|
| « Last Edit: Mar 19th, 2005, 6:49am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #1 on: Mar 18th, 2005, 12:34pm » |
Quote Modify
|
Well, I have something, at least:
Suppose 4n+1 | 4(n!)4+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)2, 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=a2+b2; we therefore want a2=1, b2=4n.
Note that 1+4r4 = (1+2r+2r2)(1-2r+2r2) = (r2+(r+1)2)(r2+(r-1)2),
and moreover that the two factors are relatively prime, since (1+2r+2r2,4r)=1.
Thus we have
p | (n!)2 + (n! +- 1)2,
and since n! is relatively prime to p,
(1 +- 1/n!)2 = -1 = (2n)!2 mod p,
and it follows
n! +- 1 = +- (2n)!n! mod p.
Then I run out of ideas. One also has
(2n!2)2 = -1 = (2n)!2 mod p,
so 2n!2 = +- (2n)!, i.e., (2n Choose n) = +- 2 mod p.
|
| « Last Edit: Mar 18th, 2005, 12:57pm by Eigenray » |
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #2 on: Mar 19th, 2005, 7:23am » |
Quote Modify
|
Quote:| Thus p=4n+1 is prime, and is therefore uniquely (up to sign and order) the sum of two squares, p=a2+b2; we therefore want a2=1, b2=4n. |
|
According to Davenport, there is a result due to Gauss that
a prime p = 4n + 1 equals a2 + b2 where a = (2n)! / [2(n!)2] (mod p)
Hope this helps.
|
| « Last Edit: Mar 19th, 2005, 11:53am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #3 on: Mar 19th, 2005, 11:17am » |
Quote Modify
|
on Mar 19th, 2005, 7:23am, THUDandBLUNDER wrote:
According to Davenport, there is a result due to Gauss that
a prime p = 4n + 1 equals a2 + b2 where a = (2n)!/[2(n!)2] (mod p)
Hope this helps. |
|
Well, that'll do it: a=+-1 mod p implies a=+-1, so b2=p-a2=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.
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #4 on: Mar 19th, 2005, 12:55pm » |
Quote Modify
|
I was afraid you would ask that.
No, I don't have the Davenport reference but I might be able to find it.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #5 on: Mar 19th, 2005, 2:29pm » |
Quote Modify
|
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!2) (mod p), y= (2k)!x (mod p),
with x and y numerically less than p/2. Then p=x2+y2. 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #6 on: Mar 20th, 2005, 12:26am » |
Quote Modify
|
Here 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!
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #7 on: Mar 31st, 2005, 6:11am » |
Quote Modify
|
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)!2 = -1 (mod p). Something simple, I'm sure...
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 4n + 1 divides 1 + 4(n!)^4
« Reply #8 on: Apr 2nd, 2005, 4:45am » |
Quote Modify
|
on Mar 31st, 2005, 6:11am, Deedlit wrote:| I'm also not sure why (2n)!2 = -1 (mod p). Something simple, I'm sure... |
|
Here is a simple demonstration.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print