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

For the following properties, show that either f(a) = 1 for all a, or f(a) = Legendre

  1. Apr 10, 2012 #1
    Let p be an odd prime. Let f(a) be a function defined for a prime to p satisfying the following properties:

    (i) f(a) only takes the values ±1.
    (ii) If a=b (mod p), then f(a)=f(b).
    (iii) f(ab) = f(a)f(b) for all a and b.

    Show that either f(a) = 1 for all a or that f(a) = ([itex]\frac{a}{b}[/itex])
     
  2. jcsd
  3. Apr 10, 2012 #2
    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    I don't even know how to start. I recognize that these properties are true for the Legendre symbol, but that's as far as I can get. Thanks!
     
  4. Apr 11, 2012 #3

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    I assume you meant to say "or that f(a)=(a/p)" (and not (a/b)).

    Anyway: notice that properties (i)-(iii) are simply saying that f is a group homomorphism from the group of units mod p to the multiplicative group {±1}. Now what do you know about the group of units mod p? There is one very important property.
     
  5. Apr 11, 2012 #4
    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    Correct, that is what I meant.

    I know that ±1 (mod p) is 1 and p-1 (mod p), but other than that, I really don't know. I'm bad at number theory :/
     
  6. Apr 11, 2012 #5

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    I was hinting at the fact that the group of units mod p is cyclic. So you have a homomorphism from a cyclic group to the group {±1} (no mod p for this latter group). What can you say about such a homomorphism?
     
  7. Apr 11, 2012 #6
    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    So then all of the values from 0 to p-1 would be mapped to either -1 or 1. If f(a) is [itex]\frac{a}{p}[/itex], then a would be mapped to -1 if it is a non-quadratic residue, and it would be mapped to 1 if it is a quadratic residue.

    Not sure if I'm on the right track here, since I don't know how the given properties ensure this is the case.
     
  8. Apr 11, 2012 #7

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    You're not using the fact that the group of units mod p is cyclic, i.e. that there is a primitive root mod p. This is the key to the solution.
     
  9. Apr 11, 2012 #8

    MathematicalPhysicist

    User Avatar
    Gold Member

    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    You only need to show that when a =x^2 mod p that f(a)=1 and otherwise f(a)=-1.

    If a=x^2 mod p then f(a)=f(x^2)=f(x)^2=1 (why?).

    Now when a ≠ x^2 mod p, f(a)≠f(x^2)=f(x)^2=1.
    Property 2 guarantees us injectivty of f modulo p.
     
  10. Apr 11, 2012 #9

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    This is sketchy. In fact f cannot possibly be injective mod p (unless p=3). Could you please explain what you mean?
     
  11. Apr 11, 2012 #10
    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege

    I follow your logic and get that f(a) = [itex]\frac{a}{p}[/itex], but what about the other condition that f(a) could = 1 for all a?
     
  12. Apr 12, 2012 #11
    Re: For the following properties, show that either f(a) = 1 for all a, or f(a) = Lege


    I think that what Morphism has been telling you all along is: ANY group homomorphism from a cyclic group to

    any other group is uniquely and completely determined once we know what that homom. maps a generator of the cyclic group to, so

    if both your homom. and Lagrange's map a generator of the group [itex]\left(\mathbb Z/ p\mathbb Z\right)^*[/itex] to the same element in the image then you're done...

    DonAntonio
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: For the following properties, show that either f(a) = 1 for all a, or f(a) = Legendre
Loading...