mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)

 Nick 2017-01-31 14:41

Basic Number Theory 17: quadratic reciprocity

Which numbers are squares?
More precisely, for which $$a$$ does there exist $$x$$ with $$x^2=a$$?
The answer depends on which number system we work in, of course.
In the real numbers, if $$a\geq 0$$ then $$a$$ is a square (put $$x=\sqrt{a}$$),
while if $$a<0$$ then it is not a square (since $$x^2\geq 0$$ for all real $$x$$),
so the squares are precisely the non-negative numbers.
It follows, for any real numbers $$x,y$$, that if $$x$$ is not a square and $$y$$ is not a square
then their product $$xy$$ [I]is[/I] a square.
This is a pattern that we shall see again shortly.

Let $$n$$ be a positive integer.
An integer $$a$$ is called a [B]quadratic residue[/B] modulo $$n$$ if there exists an integer $$x$$ such that $$x^2\equiv a\pmod{n}$$
(or, equivalently, if $$\bar{a}$$ is a square in $$\mathbb{Z}/n\mathbb{Z}$$).
As ever in modular arithmetic, the key is to understand what happens modulo the prime numbers.
And every integer is a quadratic residue modulo 2, so we focus on odd primes.

Let $$p$$ be an odd prime number.
For each integer $$a$$, we define the [B]Legendre symbol[/B] $$(\frac{a}{p})$$ as follows:
[LIST][*]if $$p$$ divides $$a$$ then $$(\frac{a}{p})=0$$.[*]If $$p$$ does not divide $$a$$ then $$(\frac{a}{p})=1$$ if $$a$$ is a quadratic residue modulo $$p$$, and -1 otherwise.[/LIST]For example, $$(\frac{-15}{5})=0$$, $$(\frac{19}{5})=1$$ and $$(\frac{3}{5})=-1$$.

[U]Proposition 99[/U]
Let $$p$$ be an odd prime number.
Then, for all integers $$a$$,
$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}.$

[U]proof[/U]
Take any integer $$a$$.
If $$p|a$$ then $$(\frac{a}{p})=0\equiv a^{\frac{p-1}{2}}\pmod{p}$$.
Suppose $$p$$ does not divide $$a$$.
Then (by corollary 40) $$a^{p-1}\equiv 1\pmod{p}$$
so (by proposition 60) $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$ or $$a^{\frac{p-1}{2}}\equiv -1\pmod{p}$$.
Now the unit group of the integers modulo $$p$$ is cyclic (by theorem 90)
so there exists an integer $$g$$ such that
$\left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{1},\bar{g},\bar{g}^2,\bar{g}^3, \ldots,\bar{g}^{p-2}\}$
with $$\bar{g}^{p-1}=\bar{1}$$.
Let $$H=\{\bar{g}^{2n}:n\in\mathbb{Z}\}$$, the set of all squares in $$(\mathbb{Z}/p\mathbb{Z})^*$$.
Then $$H$$ is the cyclic subgroup generated by $$\bar{g}^2$$ and, by proposition 86, $$H$$ has precisely $$\frac{p-1}{2}$$ elements, i.e.
$H=\{\bar{1},\bar{g}^2,\bar{g}^4,\bar{g}^6,\ldots,\bar{g}^{p-3}\}.$
As $$p$$ does not divide $$a$$, $$\bar{a}$$ is an element of $$(\mathbb{Z}/p\mathbb{Z})^*$$, so $$\bar{a}=\bar{g}^r$$ for some $$r\in\{0,1,\ldots,p-2\}$$.
If $$(\frac{a}{p})=1$$ then $$\bar{a}\in H$$ so $$r$$ is even, i.e. $$r=2s$$ for some integer $$s$$, and therefore $$\bar{a}^{\frac{p-1}{2}}=\bar{g}^{s(p-1)}=\bar{1}$$ giving $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$.
Conversely, if $$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$ then $$\bar{g}^{\frac{r(p-1)}{2}}=\bar{1}$$ and $$\bar{g}$$ has order $$p-1$$ so, by proposition 75, $$p-1$$ divides $$\frac{r(p-1)}{2}$$.
Thus $$r$$ is even and $$\bar{a}=\bar{g}^r\in H$$, hence $$(\frac{a}{p})=1$$. ∎

[U]Corollary 100[/U]
Let $$p$$ be an odd prime number.
Then, for all integers $$a,b$$, $$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$$.

[U]proof[/U]
For any integers $$a,b$$, proposition 99 gives
$\left(\frac{ab}{p}\right)\equiv (ab)^{\frac{p-1}{2}} =a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)\pmod{p}$
hence $$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$$. ∎

In particular, for any odd prime number $$p$$ and integers $$a,b$$,
if $$a$$ is not a square modulo $$p$$ and $$b$$ is not a square modulo $$p$$
then their product $$ab$$ [I]is[/I] a square modulo $$p$$ (just as with real numbers).

Recall that, for any integer $$a$$ and positive integer $$n$$, we write $$a\bmod{n}$$ for the remainder on dividing $$a$$ by $$n$$,
which is an integer in the range 0 to $$n-1$$ inclusive.

[U]Proposition 101[/U]
Let $$p$$ be an odd prime number and $$a$$ an integer not divisible by $$p$$.
Define $$A=\{a,2a,3a,\ldots,\frac{p-1}{2}a\}$$ and $$r=\#\{x\in A:x\bmod{p}>\frac{p}{2}\}$$.
Then $$(\frac{a}{p})=(-1)^r$$.

[U]proof[/U]
Each element of the set $$A$$ is congruent (modulo $$p$$) with a unique integer between $$-\frac{p}{2}$$ and $$\frac{p}{2}$$,
and no element of $$A$$ is congruent with 0 (modulo $$p$$) so all these integers are positive or negative.
Let $$r_1,r_2,\ldots,r_k$$ be the positive ones and $$-s_1,-s_2,\ldots,-s_m$$ the negative ones.
(Thus $$k,m$$ are non-negative integers with $$k+m=\frac{p-1}{2}$$ and, for each $$i\in\{1,2,\ldots,k\}$$ and each $$j\in\{1,2,\ldots,m\}$$ we have $$0<r_i<\frac{p}{2}$$ and $$0<s_j<\frac{p}{2}$$.)
Moreover, for any $$x,y\in A$$, if $$x\equiv y\pmod{p}$$ or $$x\equiv -y\pmod{p}$$ then $$x=y$$ (since $$p$$ does not divide $$a$$ or any positive integer less than $$p$$)
so $$r_1,r_2,\ldots,r_k,s_1,s_2,\ldots,s_m$$ are all distinct, and $$r=m$$.
But there are only $$\frac{p-1}{2}$$ distinct integers greater than 0 and less than $$\frac{p}{2}$$,
so the integers $$r_1,r_2,\ldots,r_k,s_1,s_2,\ldots,s_m$$ are precisely the integers $$1,2,\ldots,\frac{p-1}{2}$$ in some order,
and therefore
$a^{\frac{p-1}{2}}\left(\frac{p-1}{2}!\right) =a(2a)(3a)\ldots \left(\frac{p-1}{2}a\right) \equiv r_1r_2\ldots r_k(-s_1)(-s_2)\ldots (-s_m) =(-1)^m\left(\frac{p-1}{2}!\right)\pmod{p}.$
As $$p$$ does not divide $$\frac{p-1}{2}!$$, it follows that $$a^{\frac{p-1}{2}}\equiv (-1)^m\pmod{p}$$
hence, by proposition 99, $$(\frac{a}{p})\equiv (-1)^m\pmod{p}$$.
And $$r=m$$ (with $$p>2$$) so $$(\frac{a}{p})=(-1)^r$$. ∎

[U]Example[/U]
For which odd prime numbers $$p$$ is 2 a square modulo $$p$$?
Let $$A=\{2,4,6,\ldots,p-1\}$$.
In this case, all elements of $$A$$ are less than $$p$$, so we simply need to count how many of them are greater than $$\frac{p}{2}$$.
If $$p\equiv 1\pmod{4}$$ then the elements of $$A$$ greater than $$\frac{p}{2}$$ are $$\{\frac{p+3}{2},\frac{p+7}{2},\ldots,p-1\}$$.
There are $$\frac{p-1}{4}$$ elements here, so $$(\frac{2}{p})=(-1)^{\frac{p-1}{4}}$$ which is 1 if and only if $$p\equiv 1\pmod{8}$$.
If instead $$p\equiv 3\pmod{4}$$ then the elements of $$A$$ greater than $$\frac{p}{2}$$ are $$\{\frac{p+1}{2},\frac{p+5}{2},\ldots,p-1\}$$.
There are $$\frac{p+1}{4}$$ elements here, so $$(\frac{2}{p})=(-1)^{\frac{p+1}{4}}$$ which is 1 if and only if $$p\equiv -1\pmod{8}$$.
Conclusion: for any odd prime number $$p$$, 2 is a quadratic residue modulo $$p$$ if and only if $$p\equiv\pm 1\pmod{8}$$.

For distinct odd prime numbers $$p,q$$, we can consider whether $$p$$ is a quadratic residue modulo $$q$$ and also whether $$q$$ is a quadratic residue modulo $$p$$ and, at first sight, there is no reason why these two questions should be related.
It is one of the gems of Number Theory that there is a simple relationship between them. Before we can prove this, we need a small lemma.

[U]Lemma 102[/U]
Let $$p,q$$ be odd positive integers, $$A=\{1,2,\ldots,\frac{p-1}{2}\}$$, and $$B=\{1,2,\ldots,\frac{q-1}{2}\}$$.
Define $$U=\{(a,b)\in A\times B:aq-bp<-\frac{p}{2}\}$$ and $$W=\{(a,b)\in A\times B:aq-bp>\frac{q}{2}\}$$.
Then $$\#U=\#W$$.

[U]proof[/U]
Let $$f:A\rightarrow A$$ be the function $$a\mapsto \frac{p+1}{2}-a$$
and $$g:B\rightarrow B$$ be the function $$b\mapsto \frac{q+1}{2}-b$$.
Then $$f,g$$ are each bijective with $$f^{-1}=f$$ and $$g^{-1}=g$$.
Take any $$a\in A$$ and any $$b\in B$$.
Then
$f(a)q-g(b)p =\left(\frac{p+1}{2}-a\right)q-\left(\frac{q+1}{2}-b\right)p =\frac{q}{2}-\frac{p}{2}-(aq-bp).$
If $$(a,b)\in U$$ then $$aq-bp<-\frac{p}{2}$$ so $$\frac{q}{2}-\frac{p}{2}-(aq-bp)>\frac{q}{2}$$ and therefore $$(f(a),g(b))\in W$$.
Conversely, if $$(a,b)\in W$$ then $$aq-bp>\frac{q}{2}$$ so $$\frac{q}{2}-\frac{p}{2}-(aq-bp)<-\frac{p}{2}$$ and therefore $$(f^{-1}(a),g^{-1}(b))=(f(a),g(b))\in U$$.
Hence the function $$h:U\rightarrow W$$ given by $$(a,b)\mapsto (f(a),g(b))$$ is bijective and it follows that $$\#U=\#W$$. ∎

[U]Theorem 103[/U]
Let $$p,q$$ be distinct odd prime numbers. Then
$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) =\left(-1\right)^{\frac{(p-1)(q-1)}{4}}.$

[U]proof[/U]
Let $$A=\{1,2,\ldots,\frac{p-1}{2}\}$$ and $$B=\{1,2,\ldots,\frac{q-1}{2}\}$$.
For each $$a\in A$$, there exist unique integers $$b,r$$ such that $$aq=bp+r$$ and $$0\leq r<p$$ (by propostion 5).
Let $$s$$ be the number of $$a\in A$$ for which we get $$r>\frac{p}{2}$$.
Then $$(\frac{q}{p})=(-1)^s$$ by proposition 101.
Instead of taking the remainder $$r$$ in the range 0 to $$p-1$$ inclusive, we may take it in the range $$-\frac{p-1}{2}$$ to $$\frac{p-1}{2}$$ inclusive,
and then $$s$$ is the number of $$a\in A$$ for which we get $$r<0$$.
As the quotient $$b$$ is unique in each case, we also have $$s=\#S$$
where $$S=\{(a,b)\in\mathbb{Z}^2:a\in A,-\frac{p}{2}<aq-bp<0\}$$.
Take any $$(a,b)\in S$$.
Then $$bp>aq$$ with $$p,a,q$$ all positive so $$b>0$$ (and $$b$$ is an integer) hence $$b\geq 1$$.
Also $$bp<aq+\frac{p}{2}$$ and $$a<\frac{p}{2}$$ so $$b<\frac{q+1}{2}$$ (and $$b$$ is an integer) hence $$b\leq\frac{q-1}{2}$$.
Thus $$b\in B$$ and
$S=\{(a,b)\in A\times B:-\frac{p}{2}<aq-bp<0\}.$
In exactly the same way (swapping $$p$$ with $$q$$, $$a$$ with $$b$$ but also the order of the coordinates), if we let $$T=\{(a,b)\in A\times B:0<aq-bp<\frac{q}{2}\}$$ and $$t=\#T$$ then $$(\frac{p}{q})=(-1)^t$$.
Define
$\begin{eqnarray*} U & = & \left\{(a,b)\in A\times B:aq-bp<-\frac{p}{2}\right\} \\ V & = & \left\{(a,b)\in A\times B:-\frac{p}{2}<aq-bp<\frac{q}{2}\right\} \\ W & = & \left\{(a,b)\in A\times B:aq-bp>\frac{q}{2}\right\} \end{eqnarray*}$
Then the sets $$U,V,W$$ form a partition of $$A\times B$$ so $$\#(A\times B)=\#U+\#V+\#W$$.
For any $$a\in A$$ and any $$b\in B$$, $$p$$ does not divide $$a$$ and the primes $$p,q$$ are distinct so $$aq-bp\neq 0$$.
Thus $$\#V=\#S+\#T=s+t$$.
And by lemma 102 we have $$\#U=\#W$$ so
$s+t=\#V\equiv\#(A\times B)=\frac{p-1}{2}\cdot\frac{q-1}{2}\pmod{2}$
hence $$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)=(-1)^{s+t}=\left(-1\right)^{\frac{(p-1)(q-1)}{4}}$$. ∎

Let $$p,q$$ be distinct odd prime numbers.
If $$p\equiv 1\pmod{4}$$ or $$q\equiv 1\pmod{4}$$ (or both)
then $$(\frac{q}{p})=(\frac{p}{q})$$, and otherwise $$(\frac{q}{p})=-(\frac{p}{q})$$.

[U]proof[/U]
If $$p\equiv 1\pmod{4}$$ or $$q\equiv 1\pmod{4}$$ then $$\frac{(p-1)(q-1)}{4}$$ is even so, by theorem 103, $$(\frac{p}{q})(\frac{q}{p})=1$$ and therefore $$(\frac{q}{p})=(\frac{p}{q})$$.
If instead $$p\equiv q\equiv 3\pmod{4}$$ then $$\frac{(p-1)(q-1)}{4}$$ is odd so, by theorem 103, $$(\frac{p}{q})(\frac{q}{p})=-1$$ and therefore $$(\frac{q}{p})=-(\frac{p}{q})$$. ∎

[U]Example[/U]
Is 87 a square modulo 127?
Using corollary 100 and corollary 104, we see that
$\begin{eqnarray*} \left(\frac{87}{127}\right) & = & \left(\frac{3}{127}\right) \left(\frac{29}{127}\right) = -\left(\frac{127}{3}\right) \left(\frac{29}{127}\right) \\ & = & -\left(\frac{1}{3}\right) \left(\frac{29}{127}\right) = -\left(\frac{29}{127}\right) = -\left(\frac{127}{29}\right) \\ & = & -\left(\frac{11}{29}\right) = -\left(\frac{29}{11}\right) = -\left(\frac{7}{11}\right) \\ & = & \left(\frac{11}{7}\right) = \left(\frac{4}{7}\right)=1 \end{eqnarray*}$
so 87 is a square modulo 127.

[U]Exercises[/U]
79. Is 65 a quadratic residue modulo 31?
80. For which odd prime numbers $$p$$ is -2 a square modulo $$p$$?
81. Find all integers $$x$$ such that $$x^2\equiv 1\pmod{12}$$.
82. Let $$z$$ be a complex number such that $$z^8=1$$ but $$z^4\neq 1$$. Show that $$z+z^{-1}=\pm\sqrt{2}$$.

 All times are UTC. The time now is 13:24.