Euler's Proposition

For rational numbers $a,b\in\mathbb{Q}$ , let

$$(a,b)\cap \mathbb{Z}= \{x \in \mathbb{Z}: a\leq x \leq b\}$$

be the set of integers between $a$ and $b$ . The following lemma will help us to keep track of how many integers lie in certain intervals.

Lemma 4.3   Let $a,b\in\mathbb{Q}$ . Then for any integer $n$ ,

$$\char93 \left((a,b)\cap \mathbb{Z}\right) \equiv \char93 \left((a,b+2n)\cap \mathbb{Z}\right) \pmod{2}$$

and

$$\char93 \left((a,b)\cap \mathbb{Z}\right) \equiv \char93 \left((a-2n,b)\cap \mathbb{Z}\right) \pmod{2},$$

provided that each interval involved in the congruence is nonempty.

Note that if one of the intervals is empty, then the statement may be false; e.g., if $(a,b)=(-1/2,1/2)$ and $n=-1$ then $\char93 ((a,b)\cap \mathbb{Z}) = 1$ but $\char93 (a,b-2)\cap \mathbb{Z}= 0$ .

Proof. Let $\lceil x\rceil$ denotes the least integer $\geq x$ . Since $n>0$ ,

$$(a,b+2n) = (a,b) \cup [b,b+2n),$$

where the union is disjoint. There are $2n$ integers,

$$\lceil b\rceil, \lceil b\rceil+1, \ldots, \lceil b\rceil +2n-1,$$

in the interval $[b,b+2n)$ , so the first congruence of the lemma is true in this case. We also have

$$(a,b-2n) = (a,b)$$ minus $$[b-2n,b)$$

and $[b-2n,b)$ contains exactly $2n$ integers, so the lemma is also true when $n$ is negative. The statement about $\char93 \left((a-2n,b)\cap \mathbb{Z}\right)$ is proved in a similar manner. $\qedsymbol$

Once we have proved the following proposition, it will be easy to deduce the quadratic reciprocity law.

Proposition 4.3 (Euler)   Let $p$ be an odd prime and let $a$ be a positive integer with $p\nmid a$ . If $q$ is a prime with $q\equiv \pm p\pmod{4a}$ , then $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$ .

Proof. We will apply Lemma 4.3.1 to compute $\left(\frac{a}{p}\right)$ . Let

$$S = \left\{a, 2a, 3a, \ldots, \frac{p-1}{2}a\right\}$$

and

$$I = \left(\frac{1}{2}p,p\right) \cup \left(\frac{3}{2}p, 2p\right) \cup \cdots \cup \left(\left(b-\frac{1}{2}\right)p,bp\right),$$

where $b=\frac{1}{2}a$ or $\frac{1}{2}(a-1)$ , whichever is an integer.

We check that every element of $S$ that is equivalent modulo $p$ to something in the interval $(-\frac{p}{2},0)$ lies in $I$ . First suppose that $b=\frac{1}{2}a$ . Then

$$bp = \frac{1}{2}a p = \frac{p}{2} a > \frac{p-1}{2} a,$$

so each element of $S$ that is equivalent modulo $p$ to an element of $(-\frac{p}{2},0)$ lies in $I$ . Next suppose that $b=\frac{1}{2}(a-1)$ . Then

$$bp+\frac{p}{2} = \frac{a-1}{2}p + \frac{p}{2} = \frac{p-1+a}{2}> \frac{p-1}{2}a,$$

so $((b-\frac{1}{2})p,bp)$ is the last interval that could contain an element of $S$ that reduces to $(-\frac{p}{2},0)$ . Note that the integer endpoints of $I$ are not in $S$ , since those endpoints are divisible by $p$ , but no element of $S$ is divisible by $p$ . Thus, by Lemma 4.3.1,

$$\left(\frac{a}{p}\right) = (-1)^{\char93 (S\cap I)}.$$

To compute $\char93 (S\cap I)$ , first rescale by $a$ to see that

$$\char93 (S\cap I) = \char93 \left(\frac{1}{a} S \cap \frac{1}{a}I\right) = \char93 \left(\mathbb{Z}\cap \frac{1}{a}I\right),$$

where

$$\frac{1}{a} I = \left(\left(\frac{p}{2a},\frac{p}{a}\right) \cup ... ...}\right) \cup \cdots \cup \left(\frac{(2b-1)p}{2a},\frac{bp}{a}\right) \right),$$

$\frac{1}{a}S = \{1,2,3,4,\ldots,(p-1)/2\}$ , and the second equality is because $\frac{1}{a} I \subset (0,(p-1)/2 + 1/2]$ , since

$$\frac{pb}{a} \leq \frac{p \frac{a}{2}}{a} = \frac{p}{2} = \frac{p-1}{2}+\frac{1}{2}.$$

Write $p=4ac+r$ , and let

$$J = \left(\left(\frac{r}{2a},\frac{r}{a}\right) \cup \left(\frac{... ...\right) \cup \cdots \cup \left(\frac{(2b-1)r}{2a},\frac{br}{a}\right) \right).$$

The only difference between  $\frac{1}{a}I$ and $J$ is that the endpoints of intervals are changed by addition of an even integer, since

$$\frac{r}{2a} - \frac{p}{2a} = \frac{p}{2a} - 2c - \frac{p}{2a} = -2c.$$

By Lemma 4.3.3,

$$\nu=\char93 \left(\mathbb{Z}\cap \frac{1}{a}I\right) \equiv \char93 (\mathbb{Z}\cap J)\pmod{2}.$$

Thus $\left(\frac{a}{p}\right)=(-1)^\nu$ depends only on $r$ and $a$ , i.e., only on $p$ modulo $4a$ . Thus if $q\equiv p\pmod{4a}$ , then $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$ .

If $q\equiv -p\pmod{4a}$ , then the only change in the above computation is that $r$ is replaced by $4a-r$ . This changes $J$ into

$$K = \left(2-\frac{r}{2a},4-\frac{r}{a}\right) \cup \left(6-\frac{3r}{2a},8-\frac{2r}{a}\right) \cup \cdots$$

$$\cup \left(4b-2-\frac{(2b-1)r}{2a},4b-\frac{br}{a}\right).$$

Thus $K$ is the same as $-J$ , except even integers have been added to the endpoints. By Lemma 4.3.3,

$$\char93 (K\cap \mathbb{Z})\equiv \char93 \left(\frac{1}{a}I\cap \mathbb{Z}\right)\pmod{2},$$

so $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right)$ again, which completes the proof. $\qedsymbol$

The following more careful analysis in the special case when $a=2$ helps illustrate the proof of the above lemma, and the result is frequently useful in computations. For an alternative proof of the proposition, see Exercise 4.6.

Proposition 4.3 (Legendre symbol of $2$ )   Let $p$ be an odd prime. Then

$$\left(\frac{2}{p}\right) = \begin{cases}\hfill1 & \text{ if } p\equiv \pm 1\pmod{8}\\ -1 & \text{ if } p\equiv \pm 3\pmod{8}. \end{cases}$$

Proof. When $a=2$ , the set $S = \{a,2a,\ldots,2\cdot\frac{p-1}{2}\}$ is

$$\{ 2, 4, 6, \ldots, p-1 \}.$$

We must count the parity of the number of elements of $S$ that lie in the interval $I=(\frac{p}{2}, p)$ . Writing $p=8c+r$ , we have

$$\char93 \left(I\cap S\right) =\char93 \left(\frac{1}{2}I \cap \mathbb{Z}\right) =\char93 \left(\left(\frac{p}{4},\frac{p}{2}\right)\cap \mathbb{Z}\right)$$

$$=\char93 \left(\left(2c+\frac{r}{4}, 4c+\frac{r}{2}\right)\cap \m... ...r93 \left(\left(\frac{r}{4}, \frac{r}{2}\right)\cap \mathbb{Z}\right) \pmod{2},$$

where the last equality comes from Lemma 4.3.3. The possibilities for $r$ are $1,3,5,7$ . When $r=1$ , the cardinality is 0 , when $r=3, 5$ it is $1$ , and when $r=7$ it is $2$ . $\qedsymbol$