15

I don't know how your source arrived at the exponent, but I'll tell you one of my favorite elementary ways of getting there. added ex post facto: this is probably the elementary way that Andre alluded to Let $s = \frac{p-1}{2}$, and consider the $s$ equations $$\begin{align} 1&= (-1)(-1) \\ 2&=2(-1)^2 \\ 3&= (-3)(-1)^3 \\ 4&= 4 (-1)^4 \\ ...


10

Note that for $1 \leq a \leq p-2$, $a$ has a unique inverse between $1$ and $p-2$. $$\sum_{a=1}^{p-2}{\left(\frac{a(a+1)}{p}\right)}=\sum_{a=1}^{p-2}{\left(\frac{(\frac{a+1}{a})}{p}\right)}=\sum_{a=1}^{p-2}{\left(\frac{1+a^{-1}}{p}\right)}=\sum_{a=1}^{p-2}{\left(\frac{1+a}{p}\right)}=\sum_{a=2}^{p-1}{\left(\frac{a}{p}\right)}=-1$$ The first equality holds ...


10

Let $\zeta$ be some complex seventh root of unity, i.e. $\zeta=\zeta_\ell:=e^{2\pi \ell i/7}$, $\ell=0,1,2,\ldots,6$. The series $$ S(\zeta)=\sum_{n=1}^\infty \frac{\zeta^n}n $$ converges to $-\log(1-\zeta)$ unless $\zeta=1$ when it diverges. The way to use this is to write the Legendre symbol $\eta:n\mapsto\left(\frac n7\right)$ as a linear combination of ...


7

If $p=a^2+4b^2$ then $p\equiv 1\bmod{4}$ hence $$ \left(\frac{a}{p}\right)=\left(\frac{p}{a}\right)=\left(\frac{p-a^2}{a}\right)=\left(\frac{(2b)^2}{a}\right)=1. $$


7

We easily see that $p\equiv1\pmod4$, so for any prime factor $q\mid a$ we have, by quadratic reciprocity $$ \left(\frac pq\right)=\left(\frac qp\right). $$ OTOH we have $a^2=p-4b^2$. Therefore $$ p\equiv 4b^2=(2b)^2\pmod q $$ and $\left(\dfrac pq\right)=1$ for all those primes $q$. So all the prime factors of $a$ are QRs modulo $p$. Therefore so is $a$.


6

One can indeed use Gauss's Lemma, though there is a more elementary approach playing with factorials and using Euler's Criterion. The $(p^2-1)/8$ is excessively mysterious-looking. The "real" theorem is that $2$ is a quadratic residue of $p$ if $p\equiv \pm 1\pmod{8}$, and is a non-residue if $p\equiv \pm 3\pmod{8}$. It is not hard to verify that if $p\...


6

Fix an odd prime natural number $p$. Let $$S_p(A):=\sum_{x\in\mathbb{F}_p}\,\left(\frac{x^2+A}{p}\right)$$ for all $A\in\mathbb{F}_p^\times$, where $\mathbb{F}_p^\times$ is the group $\mathbb{F}_p\setminus\{0\}$ of units modulo $p$. Note that $$ \begin{align} S_p(A) &=\left(\frac{A}{p}\right)+\sum_{x\in\mathbb{F}_p^\times}\,\left(\frac{x^2+A}{p}\right)...


6

Hint: $n!\equiv 0 \pmod{5}$ for all $n\ge 5$.


6

The same proof as in Euler's criterion works fine for $\mathbb{F}_q$ because $\mathbb{F}_q$ is a field: If $x\ne 0$, then $x^{q-1}=1$ because of Lagrange's theorem applied to the multiplicative group $\mathbb{F}_q^\times$. Write $0=x^{q-1}-1=(x^{\frac{q-1}{2}}-1)(x^{\frac{q-1}{2}}+1)$. The map $x \mapsto x^2$ is homomorphism $\mathbb{F}_q^\times \to \...


6

Your idea is right! But note that $$\left (\frac{-3}{p}\right)=1\iff p\equiv_61$$ is a stronger and better condition than $p\equiv_3 1$, why? Look at all the numbers $n\equiv_3 1$ (that is, $n=1+3k$): $$1,\color{red}{4},7,\color{red}{10},13,\color{red}{16},19,\color{red}{22},\dots$$ Cool, now what? Notice that you alternate between even and odd numbers, ...


5

Hint: Since $c$ is a third root of unity, $c$ is a root of $x^3-1$ in $\mathbb F_p = \mathbb Z/p\mathbb Z$. Moreover, $c \neq 1$, so $c$ is a root of the polynomial obtained by factoring $x-1$ out of $x^3-1$, which is $x^2+x+1$. (Note that you can only do this factoring because $\mathbb F_p$ is an integral domain.) Use the fact that $c^2+c+1=0$ to simplify $...


5

Since you say you have read about Legendre symbol on Wikipedia, you should already know that $\left(\frac{a}{p}\right)$ is defined as $0$ if $p\mid a$ and as $\pm1$ for $p\nmid a$, depending on whether $a$ is a quadratic residue modulo $p$ or not. According to Euler's criterion, the congruence $$\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}$$ holds for any ...


5

Remember the formula for the Legendre symbol: $$\left(\frac{a}{p}\right) = a^{\frac{p - 1}{2}} \pmod p.$$ If $p = 6n + 1$, then $$\alpha = \frac{6n + 1 - 1}{2} = 3n$$ and $(-3)^\alpha = 1 \pmod p$. However, if $p = 6n - 1$, then $$\alpha = \frac{6n - 1 - 1}{2} = 3n - 1$$ and consequently $(-3)^\alpha = -1 \pmod p$.


5

The proof that $\Big(\frac{-1}{p}\Big) = \begin{cases} 1 & \text{if } p \equiv 1 \pmod 4 \\ -1 & \text{if } p \equiv 3 \pmod 4 \end{cases}$ and $\Big(\frac{2}{p}\Big) = \begin{cases} 1 & \text{if } p \equiv \pm1 \pmod 8 \\ -1 & \text{if } p \equiv \pm3 \pmod 8 \end{cases}$ are classic. The first bullet point becomes $\Big(\frac{-1}{p}\Big) ...


5

The crucial parts that you're missing are modulo and that $p$ and $q$ are primes. Let's say $p = 5$ and $q = 11$. Is 11 a square modulo 5? Maybe. Actually yes. Since $11 \equiv 1 \pmod 5$ it should not be too difficult to find a value of $x$ to satisfy $x^2 \equiv 11 \pmod 5$. Obviously 1 will do, since after all $11 \times 0 + 1 = 1$. Much more ...


4

There is less known about the non-multiplicative structure of legendre symbols. We know, that the legendre symbol is $1$ for exactly half of $\{1,\dots,p-1\}$ and $-1$ for the other half, but the way this values are distributed is not clear. The complexity of the usual computation with the laws of quadratic reciprocity is logarithmic in $p$. So you could ...


4

Actually, the main trick is that $$ (-3 | p) = (p | 3) $$ and depends on the fact that $$ 3 \equiv 3 \pmod 4. $$ Quite a time saver. I use the horizontal typesetting of the symbol, which was introduced by L. E. Dickson. The vertical style always makes me think of fractions. So, why? If $p \equiv 1 \pmod 4,$ then $$ (-3|p) = (-1|p ) \cdot (3 |p) = 1 \...


4

Hint: Try adding and one to each sum, and reindexing the sum so that it looks like an orthogonality relation for characters.


4

When you mentioned Euler's Criterion, you were nearly finished. Let $a$ be a quadratic residue of $p$. Then $$a^{(p-1)/2}\equiv 1\pmod{p}.\tag{1}$$ Multiplying by $a$ we get $$a^{(p+1)/2}\equiv a\pmod{p}.\tag{2}$$ If $p$ is of the form $4k+3$, then $\frac{p+1}{4}$ is an integer, and from (2) we obtain $$\left(a^{(p+1)/4} \right)^2\equiv a\pmod{p}.$$ ...


4

Remember that Legendre symbols are always $\pm 1$, and so square to $1$.


4

this equation is merely a slightly awkward way of saying that exactly half of the numbers $1,2,\cdots,p-1$ are quadratic residues $\mod p$


4

Denote your sum by $S$. Note: you don't need a congruence on $p$, but you do need $p>3$. Proof I: Let $s\neq 1$ be a fixed non-zero square $\pmod p$ (this requires that $p>3$.) As $r$ spans the non-zero residues, so does $sr$. Thus (working $\pmod p$): $$S=\sum_{r=1}^{p-1}\left(\frac {sr}p\right)sr=s\sum_{r=1}^{p-1}\left(\frac {r}p\right)r=s\...


4

With the transformation $x \mapsto p-x$, we find $$\sum_{x \in \mathbb{F}_p} \biggl(\frac{x^3-x}{p}\biggr) = \sum_{x\in \mathbb{F}_p} \biggl(\frac{-1}{p}\biggr)\biggl(\frac{x^3-x}{p}\biggr).$$ For $p \equiv 3 \pmod{4}$, we have $\bigl(\frac{-1}{p}\bigr) = -1$, and it follows that the sum is $0$. For $p \equiv 1 \pmod{4}$, the transformation shows that $$\...


4

Every $x\in[1,p-1]$ is invertible $\!\!\pmod{p}$ and if we denote with $x^{-1}$ its inverse we have: $$ \sum_{x=1}^{p-1}\left(\frac{x(x-1)}{p}\right) = \sum_{x=1}^{p-1}\left(\frac{x^{-1}}{p}\right)\left(\frac{x-1}{p}\right) = \sum_{x=1}^{p-1}\left(\frac{1-x^{-1}}{p}\right)=\sum_{y=1}^{p-1}\left(\frac{1-y}{p}\right) $$ that is just $$ \left(\frac{0}{p}\right)...


4

Your question about a generalization of the Legendre symbol/the quadratic reciprocity law was known as Hillbert’s 9th problem and is solved completely by class field theory , CFT for short. Here is a quick – but necessarily not short ! - glimpse at that vast magnificent landscape (for a history of CFT, see e.g. Cassels-Fröhlich, chapter XI): Given a ...


4

I am not a number theorist, but it seems that conceptually the best way to see this is group theoretic. In brief, (for $p>2$) the set of squares is a subgroup of the set of non-zero remainders mod p and this subgroup has index 2 . It is therefore normal, and the Legendre symbol is the homomorphism to the corresponding quotient group $\mathbb{Z}/2\mathbb{Z}...


4

Since the Legendre symbol is multiplicative we have: $$\left(\frac{-2}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{-1}{p}\right)$$ The first one is equal to $1$ iff $p \equiv 1,7 \pmod{8}$ and the second iff $p \equiv 1 \pmod{4}$. So they are both one when $p \equiv 1 \pmod{8}$ and both $-1$ when $p \equiv 3 \pmod{8}$. In both cases their product is one ...


4

Since $4(n^2+n+1)=(2n+1)^2+3$ is divisible by $p$, we have $-3$ is a quadratic residue mod $p$. So \begin{align*} 1=\left(\frac{-3}{p}\right)&=\left(\frac{3}{p}\right)\left(\frac{-1}{p}\right)\\ &=\left(\frac{3}{p}\right)(-1)^{(p-1)/2}\\ &=\left(\frac{p}{3}\vphantom{\frac3p}\right)(-1)^{\frac{p-1}{2}\cdot\frac{3-1}{2}}(-1)^{\frac{p-1}{2}}&&...


3

$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{((p-1)/2)((q-1)/2)}$$ multiplying both sides by $\color{blue}{\left(\frac{q}{p}\right)}$, we get $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)\color{blue}{\left(\frac{q}{p}\right)} = \color{blue}{\left(\frac{q}{p}\right)}(-1)^{((p-1)/2)((q-1)/2)}$$ Next notice that $\left(\frac{q}{p}\right)\...


3

We use Reciprocity. Suppose that $p$ is of the form $4k+1$. Then $(3/p)=(p/3)$. But $1$ is a quadratic residue of $3$ and $2$ is not. So in this case if $p\equiv 1\pmod{3}$, then $(3/p)=1$, and if $p\equiv 2\pmod{3}$, then $(3/p)=-1$. If $p\equiv 3\pmod{4}$, then $(3/p)=-(p/3)$. We conclude as above that if $p\equiv 1\pmod{3}$ then $(3/p)=-1$, and if $p\...


Only top voted, non community-wiki answers of a minimum length are eligible