# Tag Info

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