# Legendre Symbol

• Oct 30th 2010, 11:28 AM
Capillarian
Legendre Symbol
This question has completely floored me.
__________________________________

Let $\displaystyle f(x) = x^7 -2x^6-2x^5-3x^4$. Evaluate the Legendre symbol

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right)$

for all integers x.
__________________________________

I have factorised f(x) and have the following, by multiplicativity:

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right) = \left( \frac{x}{19} \right)^4 \left( \frac{x-3}{19} \right) \left( \frac{x^2 + x +1}{19} \right)$

and the first term must be +1 (as it is raised to an even power). But I've been manipulating the other two for the last two hours and have gotten pretty much nowhere. Any ideas?
• Oct 30th 2010, 08:12 PM
tonio
Quote:

Originally Posted by Capillarian
This question has completely floored me.
__________________________________

Let $\displaystyle f(x) = x^7 -2x^6-2x^5-3x^4$. Evaluate the Legendre symbol

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right)$

for all integers x.
__________________________________

I have factorised f(x) and have the following, by multiplicativity:

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right) = \left( \frac{x}{19} \right)^4 \left( \frac{x-3}{19} \right) \left( \frac{x^2 + x +1}{19} \right)$

and the first term must be +1 (as it is raised to an even power). But I've been manipulating the other two for the last two hours and have gotten pretty much nowhere. Any ideas?

$\displaystyle x^2+x+1=(x+8)(x+12)\!\!\pmod{19}$ , so taking into account your first deduction we get

$\displaystyle \left(\frac{f(x)}{19}\right)=\left(\frac{x+16}{19} \right)\left(\frac{x+8}{19}\right)\left(\frac{x+12 }{19}\right)$.

Now input all the values from $\displaystyle 0\,\,to\,\,18\!\!\pmod{19}$ , and with a list of the squares modulo 19 by your side check each output...

Tonio
• Oct 31st 2010, 07:48 AM
Capillarian
Edit: Terrible formatting. See below.
• Oct 31st 2010, 07:50 AM
Capillarian
Wonderful! Thanks so much. That question was bugging me for ages. I got the following:

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right) = \begin{Bmatrix} 0 & \text{ if } x \equiv 0, 4, 7, \text{ or } 11 (\mod 19) \\ +1 & \text{ if } x \equiv 2, 3, 8, 10, 14, \text{ or } 17 (\mod 19) \\ -1 & \text{ otherwise. } \end{matrix}$

Does that seem the right sort of thing?
• Oct 31st 2010, 07:59 AM
tonio
Quote:

Originally Posted by Capillarian
Wonderful! Thanks so much. That question was bugging me for ages. I got the following:

$\displaystyle \displaystyle \left( \frac{f(x)}{19} \right) = \begin{Bmatrix} 0 & \text{ if } x \equiv 0, 4, 7, \text{ or } 11 (\mod 19) \\ +1 & \text{ if } x \equiv 2, 3, 8, 10, 14, \text{ or } 17 (\mod 19) \\ -1 & \text{ otherwise. } \end{matrix}$

Does that seem the right sort of thing?

Why do you get zero with $\displaystyle 4\!\!\pmod {19}$ ? I get 1...Likewise, with $\displaystyle 2\!\!\pmod {19}$ I get $\displaystyle -1$ ...Check all these.

Tonio
• Oct 31st 2010, 09:01 AM
Capillarian
Quote:

Originally Posted by tonio
Why do you get zero with $\displaystyle 4\!\!\pmod {19}$ ? I get 1...Likewise, with $\displaystyle 2\!\!\pmod {19}$ I get $\displaystyle -1$ ...Check all these.

Tonio

Argh! I've accidentally written the factorization down as $\displaystyle f(x) = (x+8)(x+12)(x+15) \mod 19$ when the last term should have been 16. That's it -- I get the same answer as you now. Thanks again!