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

1. Apr 10, 2012

### 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) = ($\frac{a}{b}$)

2. Apr 10, 2012

### squire636

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!

3. Apr 11, 2012

### morphism

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.

4. Apr 11, 2012

### squire636

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

5. Apr 11, 2012

### morphism

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?

6. Apr 11, 2012

### squire636

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 $\frac{a}{p}$, 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.

7. Apr 11, 2012

### morphism

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.

8. Apr 11, 2012

### MathematicalPhysicist

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.

9. Apr 11, 2012

### morphism

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?

10. Apr 11, 2012

### squire636

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) = $\frac{a}{p}$, but what about the other condition that f(a) could = 1 for all a?

11. Apr 12, 2012

### DonAntonio

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 $\left(\mathbb Z/ p\mathbb Z\right)^*$ to the same element in the image then you're done...

DonAntonio