# MAT 338 Day 28 2011

## 2425 days ago by kcrisman

We can actually completely calculate $\left(\frac{2}{p}\right)$ with Euler's Criterion to prove that our conjecture from above is right, that

• $\left(\frac{2}{p}\right)=1$ if $p\equiv \pm 1$ mod ($8$)
• $\left(\frac{2}{p}\right)=-1$ if $p\equiv \pm 3$ mod ($8$)

We will try to show this by writing $(p-1)!$ in two different ways.

• For instance, take $p=11$.
• Then $$10!=1(2)(3)(4)(5)(6)(7)(8)(9)(10)=(2\cdot 4\cdot 6\cdot 8\cdot 10)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)$$ $$=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\, .$$
• Notice that $1,3,5$ repeat; these are all the odd numbers less than or equal to $\frac{11-1}{2}=5$.
• Now we will try to create $10!$ again from what is left.  The only ones we need to change would be $1,3,5$, as I just said.
• But $-1,-3,-5\equiv 10,8,6$ - exactly the missing pieces to $10!$.
• So I factor out $-1$ from those three, thus: $$10!=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (-1)^3\cdot (-1\cdot -3\cdot -5)\cdot (7\cdot 9)$$ $$\equiv 2^5 (-1)^3 (1\cdot 2\cdot 3\cdot 4\cdot 5)(10\cdot 8\cdot 6)(7\cdot 9)\equiv (-1)^3 2^5 (10)!$$
• Now cancel $10!$ from both sides, and we get $$1\equiv 2^5 (-1)^3\, ,$$ which means $$2^{(11-1)/2}\equiv 2^5\equiv (-1)^3\equiv -1$$ and so 2 is not a QR of 11.

Proving the general case basically follows this to its natural conclusion; there was nothing special in the above argument about $p=11$.

• After writing $(p-1)!$ and factoring out $2^{(p-1)/2}$, the "repeated" numbers will be the odd numbers between 1 and $(p-1)/2$.  Clearly the only "missing" numbers are even ones between $(p-1)/2$ and $p$, which are just the negatives of these odd numbers, so the same argument as above with $(p-1)!$ will work.
• If $p\equiv 3$ mod (4), like $p=11$, then $(p-1)/2$ is odd so there will be $$\left(\frac{p-1}{2}-1\right)\frac{1}{2}+1=\frac{p+1}{4}$$ repeated factors, as $1,3,5$ above.
• If $p\equiv 1$ mod (4) (like $p=13$), on the other hand, then $(p-1)/2$ is even and there are exactly $$\left(\frac{p-1}{2}\right)\frac{1}{2}=\frac{p-1}{4}$$ repeated factors (in that case, still $1,3,5$).
• In either case, whether the number of repeated factors ($(p+1)/4$ or $(p-1)/4$, respectively) is even or odd determines whether 2 is a quadratic residue!
• So in general:
• If $p\equiv 1$ mod (4) and $\frac{p-1}{4}$ is even, it works, so $p\equiv 1$ mod (8) DOES have 2 as a QR
• If $p\equiv 1$ mod (4) and $\frac{p-1}{4}$ is odd, it does not work, so $p\equiv 5$ mod (8) DOES NOT have 2 as a QR
• If $p\equiv 3$ mod (4) and $\frac{p+1}{4}$ is even, it works, so $p\equiv 7$ mod (8) DOES have 2 as a QR
• If $p\equiv 3$ mod (4) and $\frac{p+1}{4}$ is odd, it does not work, so $p\equiv 3$ mod (8) DOES NOT have 2 as a QR
@interact def _(p = (17,prime_range(3,100))): l = legendre_symbol(2,p) r = p%8 html("The prime $%s\equiv %s\\text{ mod }(8)$ and $\left(\\frac{2}{%s}\\right)=%s$."%(p,r,p,l))

## Click to the left again to hide and once more to show the dynamic interactive window

Let's try to calculate some Legendre symbols.  Remember, we have several interesting properties, including a sort of multiplicativity and Euler's criterion.  We proved this last time.

Proposition: If $n=ab$ is a factorization (not necessarily nontrivial) of $n$, then $n$ is a QR of $p$ precisely when either both $a$ and $b$ are QRs of $p$ or both $a$ and $b$ are not Rs of $p$.  (Hence if one of $a,b$ is and the other isn't, neither is $n$.)

In terms of Legendre symbols, it means $$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$

It is also true that $x^2\equiv a$ mod ($n$) if and only if $x^2\equiv a+n$ mod ($n$), which means that we can look at whatever residue of $a$ is convenient, or $$\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)$$ Now let's try this.

• $\left(\frac{55}{17}\right)$
• $\left(\frac{83}{17}\right)$
• $\left(\frac{45}{17}\right)$
• $\left(\frac{41}{31}\right)$
• $\left(\frac{27}{31}\right)$
• $\left(\frac{22}{31}\right)$

It turns out you can resolve theoretical questions this way too.

• For instance, we know that $1,4,9$ are all quadratic residues.
• Thus, if at least one of $2,5,10$ was also a QR, then we could guarantee that there were always consecutive quadratic residues somewhere!
• As it turns out, if $p=5$ this doesn't work, because the only (nonzero) QRs are $\pm 1$ for that prime.
• But if $p=7$, then $a=1$ and $a=9\equiv 2$ are consecutive.
• And if $p>7$ is prime, then at least one of $2,5,10$ must be a QR, since:
• If 2 and 5 both aren't, then $$\left(\frac{10}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{5}{p}\right)=(-1)(-1)=1$$ means 10 is!

Thus we see that calculation and theory must go hand in hand; they are not separate.  Now, what I did in using the Euler Criterion (EC) to find $\left(\frac{2}{p}\right)$ was to look at numbers like $2x$.  So one might ask whether something like this calculation could work with general $a$ and numbers like $ax$ to find a better theoretical result.

It turns out that this is true.  We are going to follow the steps of Gauss' protege Eisenstein here (see the appendix for how Gauss did it).  Eisenstein was yet another brilliant young mathematician who came out of nowhere but died young because he couldn't find a job which could help his chronic illness, like Abel (and probably like Galois would have done, due to his hotheadedness, if he hadn't been killed in a duel first).

We are going to try to find a different way to evaluate $\left(\frac{a}{p}\right)$ than using Euler's criterion, for $p$ an odd prime and $gcd(a,p)=1$.

First, let's introduce a new set and look at a couple properties.

• Let $E$ be the set of even numbers less than $p$.  That is, $$E=\{2,4,6,\ldots,p-1\}$$
• Now, let's call the set of multiples of $a$ by even numbers $aE$; $$aE=\{2a,4a,6a,\ldots,(p-1)a\}$$
• The set of numbers $$\{(-1)^x x\mid x\in aE\}$$ is the same as the set $E$, considered as residue classes modulo $p$.
• They are even: if $x$ is even, then $(-1)^x x$ is just $x$, while if $x$ is odd, then $(-1)^x x$ is equivalent to $p-x$, which as the difference of two odds is also even.
• If any two such numbers were the same, then for some even numbers $e$ and $e'$ we have $$(-1)^{ae}ae\equiv (-1)^{ae'}ae'$$ and since $gcd(a,p)=1$ we can remove the $a$ and get that $$e\equiv \pm e'$$
• If $e$ and $e'$ are different then $e\equiv -e'$ and $e+e'\equiv 0$; but $e+e'=2p$ is not possible since they are smaller than $p$, and $e+e'=p$ is not possible since $p$ is odd.
• Thus $e=e'$.

Now let's try to get something like in Euler's criterion.

• We would need to have $a^{(p-1)/2}$.  Notice that this is exactly the number of elements in $E$.
• So we could look at $$\prod_{e\in E}ae=a^{(p-1)/2}\prod_{e\in E}e$$
• Now let's give a name to the least positive residues modulo $p$ of each $ae$ for $e \in E$; call them $r_e$.
• Then, using the fact we proved above about $(-1)^x$ and the set $E$, we can write $$\prod_{e\in E} (-1)^{r_e}r_e\equiv \prod_{e\in E}e\equiv(-1)^{\sum_{e\in E}r_e}\prod_{e\in E}r_e$$
• So by substitution and moving the minus signs, we get that $$a^{(p-1)/2}\prod_{e\in E}e\equiv a^{(p-1)/2}(-1)^{\sum_{e\in E}r_e}\prod_{e\in E}r_e$$ which means $$a^{(p-1)/2}\equiv (-1)^{\sum_{e\in E}r_e}\; .$$
• Using Euler's criterion gives us $$\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}r_e}\; .$$

So we have reduced evaluating the Legendre symbol (and hence deciding whether things have square roots modulo $p$) to the parity of a certain sum; hopefully that's an improvement on taking powers.  Of course, it's still somewhat unwieldy, so there is a final simplification.

• Where do these $r_e$ come from anyway?  Well, for $e\in E$, they are from the division algorithm: $$ae=p\lfloor\frac{ae}{p}\rfloor+r_e$$
• So if we add them all up, we get $$\sum_{e\in E}r_e=\sum_{e\in E}ae-p\sum_{e\in E}\lfloor\frac{ae}{p}\rfloor$$
• But we only care about the parity of this sum! So we can remove the whole piece with $e$ in it, as that's all even, and we can replace the $-p$ by $1$, since they are the same modulo $2$.
• Thus we get the final form of the criterion: $$\left(\frac{a}{p}\right)=(-1)^{\sum_{e\in E}\lfloor\frac{ae}{p}\rfloor}\; .$$

Now, you might think we have to keep doing this, and that our task of finding out when numbers have square roots mod ($p$) is hopeless!  But quite the opposite is true - and next time we will derive the same result almost effortlessly using the great theorem called quadratic reciprocity!

Homework:

1. Evaluate all Legendre symbols for $p=7$ using Euler's Criterion.
2. Evaluate the Legendre symbols for $p=11$ and $a=2,3,5$ using the calculation of Eisenstein's above (immediately above, in this case!).
3. Use the previous problem, your knowledge of $\left(\frac{-1}{11}\right)$ and of perfect squares to evaluate the other Legendre symbols for $p=11$.
4. Make up several hard-looking Legendre symbols $\left(\frac{a}{29}\right)$ (modulo $p=29$) that are easy to solve by adding $p$ or by factoring $a$.
5. Use the multiplicative property of the Legendre symbol to give a congruence condition for when $\left(\frac{-2}{p}\right)=\pm 1$.
6. For $0<a,b<p$, prove that at least one of $a,b,$ and $ab$ is a quadratic residue of $p$.
7. Prove that for any prime $p$, if $1<i,j<\frac{p}{2}$ and $i\neq j$, then $i^2\not\equiv j^2$ mod ($p$).  (Hint: factor!)
8. Last class we conjectured and proved that $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .$$  Conjecture (and, if you can, prove) a similar result for $$\sum_{a\in Q_p} a\, .$$
9. Prove: if $p\equiv 3$ mod (4), and if $a\not\equiv \pm 1,0$, then $a$ is a QR if and only if $p-a$ is not a QR.
10. Verify the previous exercise for $p=23$.
11. Let $p$ be a prime of the form $p=2q+1$, where $q$ is prime (recall that $q$ is called a Germain prime in this case).  Show that every residue from 1 to $p-2$ is either a primitive root of $p$ or a quadratic residue.  (Hint: Use Euler's criterion, and ask yourself how many possible orders an element of $U_p$ can have.)

Appendix

In fact, it turns out that there is a different refinement of the Euler Criterion which can help us evaluate Legendre symbols without taking powers of $a$ at all.  We only have to check whether a certain set has even or odd cardinality.  The definition of the set is annoying, though, so here we go.

Let $p$ be an odd prime, so that $\frac{p-1}{2}$ and $\frac{p+1}{2}$ are consecutive integers which sort of divide the set of nonnegative residues in half.  Then we define, for a given integer $a$, the following four sets:

• $P=\{1,2,\ldots,\frac{p-1}{2}\}$ (which are the Positive least absolute residues)
• $N=\{-1,-2,\ldots,-\frac{p-1}{2}\}=\{\frac{p+1}{2},\frac{p+3}{2},\ldots,p-1\}$ (which are the Negative least absolute residues)
• $aP=\{a,2a,\ldots,a\frac{p-1}{2}\}$ (which are $a$ times all the elements of $P$)
• $aN=\{-a,-2a,\ldots,-a\frac{p-1}{2}\}$ (likewise for $a$ and $N$)

As the book points out, $N$ is a special case of $aP$, for $a=-1$.  Try writing out $2P$ for $p=11$ right now, as well as try to find the sets $2P\cap N$ and $2N\cap P$.  Example 7.7 on page 127 also does this.  We can do another example if that would help clear up what the four sets above are, as well as how to calculate their intersections (when nonempty).

P=set([1,2,3,4,5]) N=set([mod(-x,11) for x in P]) TwoP=set([mod(2*x,11) for x in P])
N.intersection(TwoP)
 set([8, 10, 6]) set([8, 10, 6])

As you can see, Sage can do this with some annoying syntax you might as well avoid.

Okay, now let's start multiplying.  First off, let's multiply everything in $aP$ and factor out all the $a$s: $$a(2a)(3a)\cdots (\frac{p-1}{2}a)= a^{(p-1)/2}\left(\frac{p-1}{2}\right)!$$  Now, the Euler Criterion says that $$a^{(p-1)/2}\left(\frac{p-1}{2}\right)!\equiv \left(\frac{a}{p}\right)\left(\frac{p-1}{2}\right)!\text{ mod }(p)\, .$$  So let's see if we can write the product of everything in $aP$ some other way in order to cancel out the factorial, since that would evaluate $\left(\frac{a}{p}\right)$, right?  At this point we are going to use the same trick I used above with the multiples of 2 - I am going to factor out a $-1$ from exactly the right pieces of the product $a(2a)(3a)\cdots (\frac{p-1}{2}a)$.

First off, note that for any relevant integer $x$, $x$ and $-x$ are in opposite pieces $aP$ and $aN$.  This is because if $x\equiv am\in aP$ and $-x\equiv an\in aP$ (so that $0<m,n<\frac{p-1}{2}$), then $$0=x+(-x)\equiv am+an=a(m+n)\text{ mod }(p)\, .$$ So since $p$ doesn't divide $a$, it must divide $m+n$, but we just said that $0<m,n<\frac{p-1}{2}$, which means $0<m+n<p$ - a contradiction.

But that means that if I factor out $-1$ from some element of $aP$ which is also in $N$ (e.g. if $ax=(-1)n$ for some $n\in P$), then the result is actually not in $aP$, but is now in $P$ (so it is a least positive absolute residue, e.g. $0<n<\frac{p}{2}$).  So if we factor out $-1$ from all the elements of $aP$ which are also in $N$, we will have every single element of $P$ in the product again!  This is a little tough to digest, but it is the crux of the argument.

Once we believe the last paragraph, that means $$a(2a)(3a)\cdots (\frac{p-1}{2}a)\equiv (-1)^{|aP\cap N|}\left(\frac{p-1}{2}\right)!$$  Now we combine it with the other evaluation of the product of all the elements of $aP$: $$\left(\frac{a}{p}\right)\left(\frac{p-1}{2}\right)!=a(2a)(3a)\cdots (\frac{p-1}{2}a)\equiv (-1)^{|aP\cap N|}\left(\frac{p-1}{2}\right)!\text{ mod }(p)$$ and we cancel out the factorials, getting $$\left(\frac{a}{p}\right)=(-1)^{|aP\cap N|}\text{ - the Gauss Lemma, as it is called.}$$

len(N.intersection(TwoP))
 3 3

Again, weird Sage syntax gives us the correct answer of $\left(\frac{2}{11}\right)=(-1)^{2P\cap N}=(-1)^3=-1$, which we already knew since $11\equiv 3$ mod (4).

But now we have a VERY powerful tool for evaluating lots of Legendre symbols at once.  I encourage you to read how Jones and Jones evaluate $\left(\frac{2}{p}\right)$ using the Gauss Lemma in Corollary 7.10, and to compare it to how I did it at the beginning of this lecture.  It also will enable us to prove the extremely powerful theorem of Gauss' we will discuss next time.

plist=[13,11,5,7] [(pr,legendre_symbol(3,pr)) for pr in plist]
 [(13, 1), (11, 1), (5, -1), (7, -1)] [(13, 1), (11, 1), (5, -1), (7, -1)]