Author 
Topic: Cubic Diophantine Equation (Read 1447 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Cubic Diophantine Equation
« on: Oct 31^{st}, 2008, 10:15am » 
Quote Modify

Let p = 2^{n} + 1 be a prime number. How many integer solutions mod p has the following equation: y^{2}  x^{3} + 3x  1 = 0 mod p Note: The equation was changed.

« Last Edit: Oct 31^{st}, 2008, 9:47pm by Barukh » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Diophantine Equation
« Reply #1 on: Oct 31^{st}, 2008, 3:36pm » 
Quote Modify

Well, to start with, it is the integer closest to p which is congruent to the coefficient of x^{p1} in (x^{3}3x+1)^{(p1)/2}.

« Last Edit: Oct 31^{st}, 2008, 10:19pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Cubic Diophantine Equation
« Reply #2 on: Oct 31^{st}, 2008, 9:45pm » 
Quote Modify

Sorry, I misstated the problem (which made it much harder IMHO). Let's try to go with the easier one first... Sorry for inconvenience.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Diophantine Equation
« Reply #3 on: Oct 31^{st}, 2008, 10:25pm » 
Quote Modify

Yes that is much easier. But why is p a Fermat prime? It's enough that p is not 1 mod 3. Or did you have a different proof in mind? Theorem: For a cubic polynomial f(x), the number of solutions to y^{2} f(x) mod p is congruent, mod p, to the coefficient of x^{p1} in f(x)^{(p1)/2}. But I've seen this result before so it would feel like cheating to give the proof right away. Does someone else want to try?

« Last Edit: Oct 31^{st}, 2008, 10:52pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Cubic Diophantine Equation
« Reply #4 on: Nov 1^{st}, 2008, 12:26am » 
Quote Modify

on Oct 31^{st}, 2008, 10:25pm, Eigenray wrote:It's enough that p is not 1 mod 3. Or did you have a different proof in mind? 
 No, your condition is sufficient, and the proof I had in mind uses this condition. My formulation is a special case of that. Quote:Theorem: For a cubic polynomial f(x), the number of solutions to y^{2} f(x) mod p is congruent, mod p, to the coefficient of x^{p1} in f(x)^{(p1)/2}. 
 I haven't heard about this theorem before, but after seeing it, it does make sense, and probably is based on Euler criterion for quadratic residues.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Diophantine Equation
« Reply #5 on: Nov 1^{st}, 2008, 6:31pm » 
Quote Modify

It suddenly hit me that there's a simpler solution that I didn't notice because I had been thinking about the harder problem: everything is a cube.

« Last Edit: Nov 1^{st}, 2008, 6:32pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Cubic Diophantine Equation
« Reply #6 on: Nov 2^{nd}, 2008, 8:31am » 
Quote Modify

on Nov 1^{st}, 2008, 6:31pm, Eigenray wrote: If I get you right, yes, that's the solution I had in mind. Very nice!


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Diophantine Equation
« Reply #7 on: Nov 2^{nd}, 2008, 11:50am » 
Quote Modify

Here are two related problems: how many solutions are there to: (1) y^{2} = x^{3} + ax mod p, p a Mersenne prime (2) y^{2} = x^{3} + ax^{2} mod p. Both can be answered using the theorem I quoted, but there are also more direct(?) proofs.

« Last Edit: Nov 2^{nd}, 2008, 11:51am by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Cubic Diophantine Equation
« Reply #8 on: Nov 3^{rd}, 2008, 11:38pm » 
Quote Modify

on Nov 2^{nd}, 2008, 11:50am, Eigenray wrote:Here are two related problems: how many solutions are there to: (1) y^{2} = x^{3} + ax mod p, p a Mersenne prime (2) y^{2} = x^{3} + ax^{2} mod p. 
 Assuming a 0 mod p, I get the following: 1) p 2) p  (a/p), where the last is Legendre symbol.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Diophantine Equation
« Reply #9 on: Nov 4^{th}, 2008, 11:11pm » 
Quote Modify

Yep. I thought it was interesting how the three problems can be solved individually using quite distinct arguments, or all using that one theorem I quoted.


IP Logged 



