Results 1 to 6 of 6

Math Help - quadratic residues

  1. #1
    Newbie
    Joined
    Dec 2005
    Posts
    13

    quadratic residues

    Hi everyone!
    I need to refute the following:
    the product of two numbers, which both are not a quadratic residue mod 35, is a quadratic residue mod 35.
    in other words, to find a product of those numbers which is not a quadratic residue mod 35.

    Thanks,
    RedFox (:
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,671
    Thanks
    299
    Awards
    1
    Quote Originally Posted by Red_Fox View Post
    Hi everyone!
    I need to refute the following:
    the product of two numbers, which both are not a quadratic residue mod 35, is a quadratic residue mod 35.
    in other words, to find a product of those numbers which is not a quadratic residue mod 35.

    Thanks,
    RedFox (:
    Well, it's not elegant, but it works.

    I'm using the definition that q is a quadratic residue (mod 35) if there exists an integer x, 0 < x < 35, such that x^2 = q (mod 35).

    So I made a list of all such possible q. (Simply take all possible 0<x<18, the list repeats itself backward for 17<x<36, and find q for each x.) I get that q = 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30 are all quadratic residues (mod 35).

    A counter-example is 2 and 3. Both 2 and 3 are not quadratic residues (mod 35) and neither is 2 x 3 = 6.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    If you are interesting in this...
    Switch the topic from non-residue to residue
    ---
    The product of two quadradic residues of a prime is again a quadradic residue of a prime. I made I comment about this some time ago on this forum when I realized the quadradic residues (in fact cubic, quartic, ...) residues form a group (which is why residue times residue is residue because it is closed) under multiplication modulo p. This leads us to some truly elegant results. For example, the number of quadradic,cubic,quartic,... residues always must divide p-1. I thought anyone who studied group and number theory might appreciate this because the results might be complicated to prove on an elementary level.
    Last edited by ThePerfectHacker; September 13th 2006 at 08:30 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2005
    Posts
    13

    Well...

    First, thank you very much!
    Although as you said the proof is not so elegant, however, it works.
    And about what you said - this is really interesting! I knew just about the number of quadradic residues - which is (p-1)/2. It's nice to see that for any "other" kind of residues (cubic,...) p-1 must divide the number of them.

    (:
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Red_Fox View Post
    First, thank you very much!
    Although as you said the proof is not so elegant, however, it works.
    There is no general method of finding all quadradic residues of a prime. I belive the algorithm is NP-complete.
    Therefore it is no suprise it is not elegant.


    Let me tell you a rule for mathematcians: It is not how to find the solution it is to show the solution exists!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2005
    Posts
    13

    yeah (:


    I've heard this a lot in our department...
    I'm just finishing my B.A on applied math now, so maybe in the future I will do more things as "how to find the solution".....

    TNX
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 23rd 2009, 11:25 AM
  3. Quadratic Residues
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: July 17th 2009, 08:26 PM
  4. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 4th 2009, 02:19 PM
  5. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum