Results 1 to 4 of 4

Math Help - Quadratic Congruences

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    25

    Quadratic Congruences

    Question:

    Let p be an odd prime and gcd(a,p) = gcd(b,p) =1. Prove that either all three of the quadratic congruences
    x^2= a(mod p), x^2= b(mod p), and x^2= ab(mod p)
    are solvable or exactly one of them admits a solution.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    Consider the Legendre Symbols \left(\frac{a}{p}\right) and \left(\frac{b}{p}\right);

    The symbol is completely multiplicative so \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)  \cdot\left(\frac{b}{p}\right).

    We want to prove that the number of Legendre symbols taking on value +1 is odd.

    If it is not, however, then one side of the previous equality will be +1 while the other side will be -1... contradiction. We can have e.g. \left(\frac{a}{p}\right) = 1 and \left(\frac{b}{p}\right) = 1 so \left(\frac{ab}{p}\right) = 1, etc.

    Why is the Legendre symbol multiplicative? This property follows from Euler's Criterion, which states that \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod{p}. This is proven essentially by writing a = g^k where g is a primitive root \pmod{p} and k is even iff k is a quadradic residue \pmod{p} and using Fermat's little theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    25
    I understand how you showed it was multipicative, but does that mean the equations are solvable?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    Ah well, the Legendre symbol's definition is:

    \left(\frac{a}{p}\right) =\begin{cases}0 & a\equiv 0\pmod{p}\\ +1 & a\not\equiv 0\pmod p\mbox{ and }\exists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\\ -1 & a\not\equiv 0\pmod p\mbox{ and }\nexists x\mbox{ s.t. }x^{2}\equiv a\pmod{p}\end{cases}

    By the given condition, the first case is not true.

    If you think about it, Euler's Criterion is pretty interesting. Quadratic reciprocity is nice as well!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Congruences...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 19th 2010, 03:32 PM
  2. solve quadratic congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 12th 2008, 04:12 PM
  3. [SOLVED] Quadratic Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 14th 2008, 09:43 PM
  4. Congruences classes, Quadratic Field
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 4th 2008, 07:40 PM
  5. quadratic congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 2nd 2007, 06:02 PM

Search Tags


/mathhelpforum @mathhelpforum