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

squire636

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])

squire636

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!

morphism

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.

squire636

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 :/

morphism

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?

squire636

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.

morphism

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.

MathematicalPhysicist

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.

morphism

This is sketchy. In fact f cannot possibly be injective mod p (unless p=3). Could you please explain what you mean?

squire636

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?

DonAntonio

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