wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Cubic Diophantine Equation
        
(Message started by: Barukh on Oct 31^st, 2008, 10:15am)

Title: Cubic Diophantine Equation
Post by Barukh on Oct 31^st, 2008, 10:15am

Let p = 2ⁿ + 1 be a prime number. How many integer solutions mod p has the following equation:

y² - x³ ~~+ 3x~~ - 1 = 0 mod p

Note: The equation was changed.

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Oct 31^st, 2008, 3:36pm

Well, to start with, it is the integer closest to p which is congruent to [hide]the coefficient of x^p-1 in -(x³~~-3x~~+1)^(p-1)/2.[/hide]

Title: Re: Cubic Diophantine Equation
Post by Barukh on Oct 31^st, 2008, 9:45pm

Sorry, I mis-stated the problem (which made it much harder IMHO).

Let's try to go with the easier one first...

Sorry for inconvenience.

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Oct 31^st, 2008, 10:25pm

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² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif f(x) mod p is congruent, mod p, to the coefficient of x^p-1 in -f(x)^(p-1)/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?

Title: Re: Cubic Diophantine Equation
Post by Barukh on Nov 1^st, 2008, 12:26am

on 10/31/08 at 22:25:17, 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² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif f(x) mod p is congruent, mod p, to the coefficient of x^p-1 in -f(x)^(p-1)/2.

I haven't heard about this theorem before, but after seeing it, it does make sense, and probably is based on [hide]Euler criterion for quadratic residues[/hide].

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Nov 1^st, 2008, 6:31pm

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

Title: Re: Cubic Diophantine Equation
Post by Barukh on Nov 2^nd, 2008, 8:31am

on 11/01/08 at 18:31:18, Eigenray wrote:

[hide]everything is a cube[/hide].

If I get you right, yes, that's the solution I had in mind. Very nice!

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Nov 2^nd, 2008, 11:50am

Here are two related problems: how many solutions are there to:

(1) y² = x³ + ax mod p, p a Mersenne prime ;)

(2) y² = x³ + ax² mod p.

Both can be answered using the theorem I quoted, but there are also more direct(?) proofs.

Title: Re: Cubic Diophantine Equation
Post by Barukh on Nov 3^rd, 2008, 11:38pm

on 11/02/08 at 11:50:56, Eigenray wrote:

Here are two related problems: how many solutions are there to:

(1) y² = x³ + ax mod p, p a Mersenne prime ;)

(2) y² = x³ + ax² mod p.

Assuming a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0 mod p, I get the following:

1) p
2) p - (a/p), where the last is Legendre symbol (http://en.wikipedia.org/wiki/Legendre_symbol#Definition).

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Nov 4^th, 2008, 11:11pm

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.