Results 1 to 2 of 2

Math Help - 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
    <br />
ax^2  + bx + c \equiv 0\left( {\bmod .p} \right)<br />
if and only if (multiple by 4a): <br />
4a^2 x^2  + 4abx + 4ac \equiv 0\left( {\bmod .p} \right)<br />
-the 'if and only if' is true since (4a, p)=1 - or equivalently: <br />
\left( {2ax + b} \right)^2  + 4ac \equiv b^2 \left( {\bmod .p} \right)<br />
that is <br />
\left( {2ax + b} \right)^2 \equiv b^2 -4ac\left( {\bmod .p} \right)<br />
(1)

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

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

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

    2. If <br />
\left( {\tfrac{{b^2  - 4ac}}<br />
{p}} \right) = 1<br />
we have <br />
b^2  - 4ac \equiv y^2 \left( {\bmod .p} \right)<br />
for some 0<y<p and it is enough to take: <br />
2ax + b \equiv y\left( {\bmod .p} \right)<br />
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: November 4th 2010, 09:44 PM
  2. Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: March 30th 2010, 02:57 PM
  3. Euler's criterion
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 17th 2009, 05:29 AM
  4. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 03:59 PM
  5. need help on quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 15th 2009, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum