Results 1 to 3 of 3

Math Help - quadratic residue proof

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    Chapel Hill, NC
    Posts
    2

    Talking quadratic residue proof

    1) If ab=r mod p, where r is a quadratic residue of the odd prime p, prove that a & b are both quadratic residues of p or both non-residues of p.

    2) If a and b are both quadratic residues of the odd prime p, or both non-residues of p, show that the congruence ax2=b mod p has a solution [hint: multiply the given congruence by a', where aa'=1 mod p]

    Need all the help i can get... pretty stuck. Thanks !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,308
    Thanks
    686

    Re: quadratic residue proof

    lazy proof of (1):

    suppose a = x2 (mod p), and b = y2 (mod p).

    then ab = x2y2 = (xy)2 (mod p).

    the quadratic residues form a subgroup of the non-zero residues (mod p), this is a finite set, and we have closure.

    now since p is an odd prime, (p-1)/2 is an integer.

    by fermat's little theorem, ap-1 = 1 (mod p), thus:

    (a(p-1)/2)2 = ap-1 = 1 (mod p).

    hence a(p-1)/2 is either of order 1 (that is = 1), or order 2 (that is = -1 = p - 1 (mod p) (Zp)* is cyclic, so there is a unique element of order 2).

    this creates a homomorphism (the legendre symbol homomorphism) from (Zp)* to {-1,1}.

    the kernel of this homomorphism is the quadratic residues, which is therefore a (normal) subgroup of index 2.

    if we call this subgroup Q, we see the non-quadratic residues are "the other coset" xQ, for some non-residue x.

    thus:
    1. QQ = Q
    2.Q(xQ) = (1x)Q = xQ
    3.(xQ)Q = (x1)Q = xQ
    4.(xQ)(xQ) = x2Q = Q (since x2 is clearly a quadratic residue).

    this is what we set out to prove.

    for example, with p = 7 (working mod 7):

    12 = 1
    22 = 4
    32 = 2
    42 = 2 (not surprising: 4 = -3, and (-3)(-3) = (-1)(3)(-1)(3) = (-1)(-1)(3)(3) = (3)(3))
    52 = 4
    62 = 1

    so Q = {1,2,4} ((7-1)/2 = 6/2 = 3 elements) and we may take x = 3, so 3Q = {3,6,5} (this is the same set as 5Q, or 6Q).

    now (2) is straightforward:

    a-1(ax2) = a-1b <---the RHS is in Q, by (1).

    (a-1a)x2 = a-1b,

    x2 = a-1b (and we have a solution since a-1b is in Q, that is aQ and bQ are the same coset).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2012
    From
    Chapel Hill, NC
    Posts
    2

    Re: quadratic residue proof

    wow, thanks so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof with quadratic residue
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 17th 2011, 03:17 PM
  2. [SOLVED] Quadratic Residue proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 13th 2011, 04:10 PM
  3. When is 2 a quadratic residue?
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 8th 2011, 05:49 PM
  4. Quadratic Residue Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 24th 2010, 09:32 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum