Results 1 to 4 of 4

Math Help - Quadratic Congruence

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    2

    Question Quadratic Congruence

    Question: Let p be an odd prime and gcd(a, p) = 1. Establish that the quadratic congruence ax^2 + bx + c = 0 (mod p) is solvable if and only if b^2 - 4ac is either zero or a quadratic residue of p.

    Here's what I have so far:
    [If] Assume that ax^2 + bx + c = 0 (mod p) is solvable.
    Since p is an odd prime, gdp(4a, p) = 1. So the quadratic congruence is equivalent to 4a(ax^2 + bx + c) = 0 (mop p). 4a(ax^2 + bx + c) = (2ax + b)^2 - (b^2 - 4ac), so (2ax + b)^2 = (b^2 - 4ac) (mod p). Let y = (2ax + b) and d = (b^2 - 4ac), so y^2 = d (mod p).
    If (2ax + b)^2 = (b^2 - 4ac) (mod p) has a solution, (b^2 - 4ac) is a quadratic residue of p. Does this make any sense?
    Now, I don't know how to show that (b^2 - 4ac) can also be zero.

    [Only If] Assume that (b^2 - 4ac) is either 0 or a quadratic residue of p.
    For this proof, I don't even know how to start it. I was thinking about using Euler's criterion, so (b^2 - 4ac)^((p - 1)/2) = 1 (mod p), but I'm not sure if gcd((b^2 - 4ac), p) = 1 or not and I'm not sure if this is the right way to go, and if it is, how to proceed further. And what do I do with (b^2 - 4ac) = 0?

    Any form of help if greatly appreceated.
    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by firicle View Post
    Question: Let p be an odd prime and gcd(a, p) = 1. Establish that the quadratic congruence ax^2 + bx + c = 0 (mod p) is solvable if and only if b^2 - 4ac is either zero or a quadratic residue of p.

    Here's what I have so far:
    [If] Assume that ax^2 + bx + c = 0 (mod p) is solvable.
    Since p is an odd prime, gdp(4a, p) = 1. So the quadratic congruence is equivalent to 4a(ax^2 + bx + c) = 0 (mop p). 4a(ax^2 + bx + c) = (2ax + b)^2 - (b^2 - 4ac), so (2ax + b)^2 = (b^2 - 4ac) (mod p). Let y = (2ax + b) and d = (b^2 - 4ac), so y^2 = d (mod p).
    If (2ax + b)^2 = (b^2 - 4ac) (mod p) has a solution, (b^2 - 4ac) is a quadratic residue of p. Does this make any sense?
    Now, I don't know how to show that (b^2 - 4ac) can also be zero.

    [Only If] Assume that (b^2 - 4ac) is either 0 or a quadratic residue of p.
    For this proof, I don't even know how to start it. I was thinking about using Euler's criterion, so (b^2 - 4ac)^((p - 1)/2) = 1 (mod p), but I'm not sure if gcd((b^2 - 4ac), p) = 1 or not and I'm not sure if this is the right way to go, and if it is, how to proceed further. And what do I do with (b^2 - 4ac) = 0?

    Any form of help if greatly appreceated.
    Thanks in advance

    Much simpler, in my opinion: since (a,p)=1\,,\,\,a is invertible in \mathbb{F}_p:=\mathbb{Z}\slash\mathbb{Z}_p and thus you can freely use the well-known high-schoolish formula to find

    the zeroes of a quadratic equation: x_{1,2}=\frac{-b\pm \sqrt{\Delta}}{2a}\,,\,\,\Delta=b^2-4ac ...UNLESS p=2 , but then ax^2+bx+c=x^2+bx+c , and this can simply be solved (or not) by direct inspection.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    2

    Question

    Quote Originally Posted by tonio View Post
    Much simpler, in my opinion: since (a,p)=1\,,\,\,a is invertible in \mathbb{F}_p:=\mathbb{Z}\slash\mathbb{Z}_p and thus you can freely use the well-known high-schoolish formula to find

    the zeroes of a quadratic equation: x_{1,2}=\frac{-b\pm \sqrt{\Delta}}{2a}\,,\,\,\Delta=b^2-4ac ...UNLESS p=2 , but then ax^2+bx+c=x^2+bx+c , and this can simply be solved (or not) by direct inspection.

    Tonio
    I realize that b^2 - 4ac is taken from the quadratic equation, but this is a congruence -- it works well with addtion and multiplication, but division and taking the square root can't be done, and cancellation of a
    common factor on both sides of a congruence can only be done
    in proper circumstances. Right? (This is something I got from my notes, my textbook and from what my prof said.)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by firicle View Post
    I realize that b^2 - 4ac is taken from the quadratic equation, but this is a congruence -- it works well with addtion and multiplication, but division and taking the square root can't be done, and cancellation of a
    common factor on both sides of a congruence can only be done
    in proper circumstances.


    EVERYTHING in this world can be done ONLY in proper circumstances...

    What your congruence modulo p says is that the quadratic equals zero in \mathbb{F}_p and thus you can freely use the given formula.

    And all the arithmetic operations , up to and including roots, can be done modulo p "under the proper circumstances" (for example, never dividing by zero...)

    Tonio

    Right? (This is something I got from my notes, my textbook and from what my prof said.)

    Thanks
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic congruence - proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 29th 2010, 01:08 PM
  2. quadratic congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 24th 2010, 06:54 AM
  3. quadratic congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2009, 04:02 PM
  4. quadratic congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2009, 11:14 PM
  5. computing quadratic congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 7th 2008, 12:58 AM

Search Tags


/mathhelpforum @mathhelpforum