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

Challenge problem from class

  1. May 6, 2004 #1

    qaz

    User Avatar

    show that the polynomial [itex]g(x)=(x^2 -5) (x^2-41)(x^2-205)[/itex] has a solution modulo any integer [itex]n[/itex]∈ℕ.
     
  2. jcsd
  3. May 6, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    you mean root; if there is a solution it should come from considering quadratic residues, i imagine.
     
  4. May 7, 2004 #3

    qaz

    User Avatar

    ok, but i am stil stuck i dont know where to go from here...we dont have a good book for this class and it wasnt explained well at all.
     
  5. May 7, 2004 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you done anything? (whether successful or not)

    Sometimes starting small helps. What has to be true for some number m to be a root of g, mod n? What has to be true if no such m exists?
     
  6. May 8, 2004 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Have you also noticed something important about 205?

    What do you konw about Legendre's Symbol? I'm sure there are lots of useful resources out there, try Wolfram.
     
  7. May 9, 2004 #6

    qaz

    User Avatar

    ok, i know that 205 can be written as the following: (205/n)=(5/n)(41/n), which reduces to =(-1)(-1)=1. so there are either 2 cases for this problem, (5/n)=1 or (41/n)=1.
     
  8. May 10, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    that is possibly correct in spirit, but needs better explanation: at least one of 5,41 or 41*205 must be a quadratic residue mod n for each n because...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?