Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding solutions

  1. Apr 10, 2005 #1
    find the number of solutions in z103

    x^2==22(mod103)
     
  2. jcsd
  3. Apr 10, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Have you seen quadratic reciprocity?
     
  4. Apr 10, 2005 #3
    no i haven't
     
  5. Apr 10, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Legendre symbol?
     
  6. Apr 13, 2005 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    The Legendre symbol [tex]\left(\frac{a}{p}\right)[/tex] is defined as 1 if [tex]x^2\equiv a\pmod p[/tex] has solutions, and -1 otherwise. (It's undefined or 0 if [tex]p\mid a[/tex].)

    Thus for [tex]x^2\equiv22\pmod{103}[/tex] you're trying to decide the value of the Legendre symbol [tex]\left(\frac{22}{103}\right)[/tex].

    Here's the 3-part Law of Quadratic Reciprocity:

    [tex]\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}[/tex]

    [tex]\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}[/tex]

    [tex]\left(\frac{a}{p}\right)=(-1)^{\frac{(p-1)(a-1)}{4}}\left(\frac{p}{a}\right)[/tex]

    (If you're using a definition that doesn't include 0, you can move the two Legendre symbols to the same side for aesthetics.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Finding solutions
Loading...