Results 1 to 2 of 2

Thread: Quadratic Reciprocity/ Euler's Criterion

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    25

    Quadratic Reciprocity/ Euler's Criterion

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    $\displaystyle
    ax^2 + bx + c \equiv 0\left( {\bmod .p} \right)
    $ if and only if (multiple by 4a): $\displaystyle
    4a^2 x^2 + 4abx + 4ac \equiv 0\left( {\bmod .p} \right)
    $ -the 'if and only if' is true since (4a, p)=1 - or equivalently: $\displaystyle
    \left( {2ax + b} \right)^2 + 4ac \equiv b^2 \left( {\bmod .p} \right)
    $ that is $\displaystyle
    \left( {2ax + b} \right)^2 \equiv b^2 -4ac\left( {\bmod .p} \right)
    $(1)

    From here it is obvious that $\displaystyle
    ax^2 + bx + c \equiv 0\left( {\bmod .p} \right)
    $ implies either $\displaystyle
    p|(b^2 - 4ac)
    $ or $\displaystyle
    \left( {\tfrac{{b^2 - 4ac}}
    {p}} \right) = 1
    $

    Conversely if either $\displaystyle
    p|(b^2 - 4ac)
    $ or $\displaystyle
    \left( {\tfrac{{b^2 - 4ac}}
    {p}} \right) = 1
    $ we can see that our congruence is solvable as follows:

    1. If $\displaystyle
    p|(b^2 - 4ac)
    $ our congruence ( remember (1) ) holds if $\displaystyle
    \left( {2ax + b} \right)^2 \equiv 0\left( {\bmod .p} \right)
    $ now $\displaystyle 2ax\equiv{-b}(\bmod.p)$ is solvable since (2a, p)=1. Thus our congruence is solvable.

    2. If $\displaystyle
    \left( {\tfrac{{b^2 - 4ac}}
    {p}} \right) = 1
    $ we have $\displaystyle
    b^2 - 4ac \equiv y^2 \left( {\bmod .p} \right)
    $ for some $\displaystyle 0<y<p$ and it is enough to take: $\displaystyle
    2ax + b \equiv y\left( {\bmod .p} \right)
    $ which is solvable since (2a, p)=1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's criterion
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Nov 4th 2010, 08:44 PM
  2. Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Mar 30th 2010, 01:57 PM
  3. Euler's criterion
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 17th 2009, 04:29 AM
  4. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 02:59 PM
  5. need help on quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 15th 2009, 01:01 PM

Search Tags


/mathhelpforum @mathhelpforum