Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [legendre-symbol]

For questions involving the Legendre symbol, $\genfrac{(}{)}{}{}{a}{p}$ for integer $a$ and prime $p$.

In number theory, the Legendre symbol is a multiplicative function with values $1, −1, 0$ that is a quadratic character modulo a prime number $p$: its value on a (nonzero) quadratic residue mod p is 1 and on a non-quadratic residue (non-residue) is $−1$. Its value on zero is $0$.

The Legendre symbol was introduced by Adrien-Marie Legendre in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol.

Source: https://en.wikipedia.org/wiki/Legendre_symbol

302 questions
3
votes
1 answer

Proof that Legendre symbol $\Big(\frac{a}{p}\Big)$ is $a^{\frac{p-1}{2}}$

When $p$ is a prime, we know that Legendre symbol of $a$ is $$\left(\frac{a}{p}\right) = a^{({p-1})/{2}}$$ Suppose $a$ is a square, then $a = x^2$ for some $x$. Therefore, $a^{\frac{p-1}{2}} = x^{p-1} = 1$ by Fermat's little theorem. But if $a$ is…
satya
  • 145
1
vote
1 answer

How does Legendre symbol formula $(-1)^{{p-1\over 2}{q-1\over 2}}$, actually show the correct value?

I've read about this formula on wikipedia, but attempting to use it just gets me: $$q\equiv 3 \bmod 4\implies p\equiv 1 \mod 4 $$ and$$q\equiv 1 \bmod 4\implies p\equiv 1,3 \mod 4.$$ However, $$1,4,9,3,12,10\equiv x^2\bmod 13 19$$ disproves this. I…
user645636
0
votes
1 answer

Legendre's proof involving linearity independence

Show that any polynomial of degree n is a linear combination of P0(x), P1(x), ..., Pn(x) Actually I have no idea how to start with a proof involving "any". Can someone help??
user635977
  • 11
0
votes
1 answer

Proof problem : show that $\frac{n_{1}n_{2}-1}{2}$ = $\frac{n_{1}-1}{2}$ + $\frac{n_{2}-1}{2}$ mod(2)

I want to show that, for odd positive integers $n_{1}$ and $n_{2}$, we have : $\frac{n_{1}n_{2}-1}{2}$ = $\frac{n_{1}-1}{2}$ + $\frac{n_{2}-1}{2}$ mod(2) Let $n_{1}$ = ${2m_{1} +1}$ and $n_{2}$ = ${2m_{2} +1}$ I get : 2${m_{1}m_{2}} + {m_{1}} +…
miskinalien
  • 3
0
votes
1 answer

Legendre Symbol sum

Let $p \equiv 3 \pmod 8$. Show: $\sum_{a=1}^{p-1} a\Big(\frac{a}{b}\Big)=\sum_{a=1}^{(p-1)/2} (2a-p)\Big(\frac{a}{b}\Big)$ and $\sum_{a=1}^{p-1} a\Big(\frac{a}{b}\Big)=\sum_{a=1}^{(p-1)/2} (p-4a)\Big(\frac{a}{b}\Big)$ I manged to prove the first…
Patrick
  • 419
-1
votes
1 answer

Verification: have I worked this legendre symbol correctly

Compute $(\frac{92}{11}$). Now $92^2 \equiv x^2\ mod(11) $ Now since there is no such x that satisfies this, so the legendre symbol is $-1$. Is this right? Also, can somebody explain in a slightly more layman's language what the significance of…
stackdsewew
  • 1,047