```

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 31st, 2008, 10:15am)

```

Title: Cubic Diophantine Equation
Post by Barukh on Oct 31st, 2008, 10:15am
Let p = 2n + 1 be a prime number.  How many integer solutions mod p has the following equation:

y2 - x3 + 3x - 1 = 0 mod p

Note: The equation was changed.

Title: Re: Cubic Diophantine Equation
Post by Eigenray on Oct 31st, 2008, 3:36pm
Well, to start with, it is the integer closest to p which is congruent to [hide]the coefficient of xp-1 in -(x3-3x+1)(p-1)/2.[/hide]

Title: Re: Cubic Diophantine Equation
Post by Barukh on Oct 31st, 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 31st, 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 y2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif f(x) mod p is congruent, mod p, to the coefficient of xp-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 1st, 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 y2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif f(x) mod p is congruent, mod p, to the coefficient of xp-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 1st, 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 2nd, 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 2nd, 2008, 11:50am
Here are two related problems: how many solutions are there to:

(1) y2 = x3 + ax mod p, p a Mersenne prime ;)

(2) y2 = x3 + ax2 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 3rd, 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) y2 = x3 + ax mod p, p a Mersenne prime ;)(2) y2 = x3 + ax2 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 4th, 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.