| | |
Comparing the values of $(p,q)$ and $(q,p)$ for distinct odd primes $p$ and $q$ can easily lead one to conjecture the following: $$\left(\frac{p}{q}\right) \neq \left(\frac{q}{p}\right) \textrm{ if and only if }\, p,q \equiv 3\pmod{4}$$
This turns out to be one of the most celebrated theorems in number theory - however, it's proof can be challenging. As such, let's first look at a specific example to motivate our argument..
Suppose $p = 23$ and $q = 17$, and we wish to investigate $(23/17)$ and $(17/23)$
In evaluating $(17/23)$...
Using Gauss' Lemma, one looks at the even least residues modulo $23$ of products of the form $17 \cdot a$, where $a$ is odd and $0 < a < 23$, as shown below: $$\require{color} \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} \textrm{odd } a \textrm{ strictly between } 0 \textrm{ and } 23& 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21\\\hline \textrm{least residue modulo 23 of }(17 \cdot a) & 17 & 5 & {\color{red}\fbox{16}} & {\color{red}\fbox{4}} & 15 & 3 & {\color{red}\fbox{14}} & {\color{red}\fbox{2}} & 13 & 1 & {\color{red}\fbox{12}} \end{array}$$
For convenience, let ${\color{red}S} = \{{\color{red}16},{\color{red}4}, {\color{red}14}, {\color{red}2}, {\color{red}12}\}$ be the set of these even least residues, and note that applying Gauss' Lemma we quickly have $(17/23) = (-1)^{|{\color{red}S}|} = (-1)^5 = -1$.
Similarly, to evaluate $(23/17)$...
One looks at the even least residues modulo $17$ in the set of products of the form ${23 \cdot a'}$, where $a'$ is odd and $0 < a' < 17$, as shown: $$\begin{array}{c|c|c|c|c|c|c|c|c} \textrm{odd } a' \textrm{ strictly between } 0 \textrm{ and } 17& 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15\\\hline \textrm{least residue modulo 17 of }(23 \cdot a') & {\color{blue}\fbox{6}} & 1 & 13 & {\color{blue}\fbox{8}} & 3 & 15 & {\color{blue}\fbox{10}} & 5 \end{array}$$
In a like manner, let ${\color{blue}S'} = \{{\color{blue}6},{\color{blue}8},{\color{blue}10}\}$ be this last set of even least residues, and note that $(23/17) = (-1)^{|{\color{blue}S'}|} = (-1)^3 = -1$.
First, notice that by virtue of being residues in their respective moduli, every $s \in S$ necessarily takes the form $s = 23k+17a$ where $a$ is odd and $k$ is some integer, while every $s' \in S'$ takes the form $s' = 23a'+17k'$ where $a'$ is odd and $k'$ is some integer.
We can say a bit more upon noticing that both the $k$ and $k'$ mentioned above must both be odd. To see this, note that $s = 23k+17a$, $s$ even, and $a, 17,$ and $23$ odd forces $k$ to be odd, while similarly, $s' = 23a'+17k'$, $s'$ even, and $a', 17,$ and $23$ odd forces $k'$ to be odd.
As such, every element in both ${\color{red}S}$ and ${\color{blue}S'}$ can be written in the form of $23x+17y$ where $x$ and $y$ are both odd.
Note that for odd $x$ and $y$ values that share the same sign, $23x+17y$ has magnitude too large to result in a value from either ${\color{red}S}$ or ${\color{blue}S'}$.
As such, we could only consider numbers of the form $23x+17y$ where $x$ and $y$ are odd integers of opposite sign. Alternatively, we could limit our attention to numbers of the form $23x-17y$ where $x$ and $y$ are odd positive integers. Choosing to do the latter, consider the table below showing all values of this form, where $0 < x < 17$ and $0 < y < 23$:
$$\begin{array}{c|c|c|c|c|c|c|c|c|} & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15\\\hline 1 & {\color{blue}\fbox{6}} & 52 & 98 & 144 & 190 & 236 & 282 & 328\\\hline 3 & -28 & 18 & 64 & 110 & 156 & 202 & 248 & 294\\\hline 5 & -62 & {\color{red}\fbox{-16}} & 30 & 76 & 122 & 168 & 214 & 260\\\hline 7 & -96 & -50 & {\color{red}\fbox{-4}} & 42 & 88 & 134 & 180 & 226\\\hline 9 & -130 & -84 & -38 & {\color{blue}\fbox{8}} & 54 & 100 & 146 & 192\\\hline 11 & -164 & -118 & -72 & -26 & 20 & 66 & 112 & 158\\\hline 13 & -198 & -152 & -106 & -60 & {\color{red}\fbox{-14}} & 32 & 78 & 124\\\hline 15 & -232 & -186 & -140 & -94 & -48 & {\color{red}\fbox{-2}} & 44 & 90\\\hline 17 & -266 & -220 & -174 & -128 & -82 & -36 & {\color{blue}\fbox{10}} & 56\\\hline 19 & -300 & -254 & -208 & -162 & -116 & -70 & -24 & 22\\\hline 21 & -334 & -288 & -242 & -196 & -150 & -104 & -58 & {\color{red}\fbox{-12}}\\\hline \end{array}$$
Notice that all of the values in ${\color{blue}S'}$ appear in this group of values, as do the negatives of all of the values in ${\color{red}S}$. Indeed, taken together, these are precisely the values $t$ in the table, where $-p \lt t \lt q$. Let us refer to the set of these values as $T$.
Notice also that there is a subtle rotational symmetry to the boxed values in the table, in that if the value corresponding to $x$ and $y$ is boxed, then so is the value corresponding to $17-1-x$ and $23-1-y$. In this way, the members of $T$ can be paired up: $({\color{blue}6},{\color{red}-12})$, $({\color{red}-16},{\color{blue}10})$, $({\color{red}-4},{\color{red}-2})$, and $({\color{blue}8},{\color{red}-14})$. For clarity, note that it need not be the case that one element of any given pair be related to ${\color{red}S}$, while the other be related to ${\color{blue}S'}$, as the third pair in this example demonstrates.
Looking ahead, proving these last two observations will be the linchpin of our argument, as the symmetry forces the total number of boxed values (i.e., $|T| = |{\color{red}S}|+|{\color{blue}S'}|$) to be even, unless there is a boxed value in the center of the table that pairs with itself (which we will be able to show happens if and only if the primes $p$ and $q$ involved are both congruent to $3$ modulo $4$). Once we have established $|T| = |{\color{red}S}| + |{\color{blue}S'}|$ is even when $p$ and $q$ are not both $3$ modulo $4$, and odd otherwise, the rest of the proof will follow almost immediately from Gauss' Lemma.
With these guiding thoughts in mind, we are now ready for the formal proof.
Suppose $p$ and $q$ are distinct odd primes.
Let $S$ be the set of even least residues $s$, where $s \equiv qa\pmod{p}$, where $a$ is odd and $0 \lt a \lt p$.
Similarly, let $S'$ be the set of even least residues $s'$, where $s' \equiv pa'\pmod{q}$, where $a'$ is odd and $0 \lt a' \lt q$.
Recall, from Gauss' Lemma we know $(p/q) = (-1)^{|S|}$ and $(q/p) = (-1)^{|S'|}$. So when these two expressions agree in value, $(-1)^{|S|+|S'|} = +1$, and when they disagree, $(-1)^{|S|+|S'|} = -1$. Thus, we seek to show $|S| + |S'|$ is odd when $p,q \equiv 3\pmod{4}$ and even otherwise.
Let $T$ be the set of linear combinations $t = px - qy$ where $x$ and $y$ are odd, $0 \lt x \lt q$, $0 \lt y \lt p$, and $-p \lt t \lt q$. Then let $T^+$ be the set of positive elements of $T$, and $T^-$ be the set of negative elements of $T$. Note that $0 \not\in T$, as otherwise $0 = px - qy$ for some appropriate integers $x$ and $y$, leading to $px = qy$ which in turn would require $p \mid y$ and $q \mid x$, both of which are impossible given that $0 \lt x \lt q$ and $0 \lt y \lt p$. As such, $T^+$ and $T^-$ partition the elements of $T$ into two disjoint sets.
We intend to show $|T^-| = |S|$ and $|T^+| = |S'|$, yielding $|T| = |S| + |S'|$. To that end, we make the following claims:
Let's consider each of these in turn,
Recall every $s \in S$ is an even least residue $s \equiv qa\pmod{p}$ for some odd $a$ where $0 \lt a \lt p$. The congruence just mentioned requires the existence of some integer $x$ so that $qa - s = px$, and consequently we can find integers $x$ and $y$ so that $-s = px - qy$. In particular, $y = a$ is odd, with $0 \lt y \lt p$. It remains to show $x$ is odd, $0 \lt x \lt q$, and $-p \lt -s \lt 0$. To this end, note that knowing $s = px - qy$ with $s$ even and $p$, $q$, and $y$ all odd forces $x$ to be odd.
Now by virtue of $s$ being a least residue modulo $p$, we have $0 \le s \lt p$. However, $s = 0$ would imply that $px - qy = 0$, or equivalently $px = qy$. Since $p$ and $q$ are distinct primes, this in turn would suggest $p \mid y$ which is impossible as $0 \lt y \lt p$. Thus, we can make the stronger statement that $0 \lt s \lt p$. This in turn requires $-p \lt -s \lt 0$, which is one of the things we needed to show.
We can push our argument still further, however. Substituting for $-s$, we have $-p \lt px - qy \lt 0$. Recalling that $0 \lt y \lt p$, replacing $y$ with $p$ will only make the middle expression smaller, so $px - qp \lt 0$. Dividing by $p$, we quickly arrive at $x \lt q$. Similarly, replacing $y$ instead by $0$ only makes that middle expression bigger, so $-p \lt px -q \cdot 0$, which quickly leads to $-1 \lt x$. Recalling that $x$ must be odd, we can strengthen this to $0 \lt x$. Putting things together, we have $0 \lt x \lt q$.
As such, $s \in S$ implies $-s \in T^-$.
Arguing the other direction, suppose $-t \in T^-$. We then know there exist odd integers $x$ and $y$ so that $-p \lt -t = px - qy \lt 0$ with $0 \lt x \lt q$ and $0 \lt y \lt p$. Consequently, $0 \lt t = qy - px \lt p$. Additionally, note that as $t$ is the difference of two odd products, it must be even. Thus $t$ is an even least residue modulo $p$ of the product $qy$, where $y$ is odd and $0 \lt y \lt p$.
As such, $t \in S$.
Proving the second claim strongly parallels the proof of the first:
Recall every $s' \in S'$ is an even least residue $s' \equiv pa'\pmod{q}$ for some odd $a'$ where $0 \lt a' \lt q$. The congruence just mentioned requires the existence of some integer $y$ so that $pa' - s' = qy$, and consequently we can find integers $x$ and $y$ so that $s' = px - qy$. In particular, $x = a'$ is odd, with $0 \lt x \lt q$. It remains to show $y$ is odd, $0 \lt y \lt p$, and $0 \lt s' \lt q$. To this end, note that knowing $s' = px - qy$ with $s$ even and $p$, $q$ and $x$ all odd forces $y$ to be odd.
Now by virtue of $s'$ being a least residue modulo $q$, we have $0 \le s' \lt q$. However, $s' = 0$ would imply that $px - qy = 0$, or equivalently $px = qy$. Since $p$ and $q$ are distinct primes, this in turn would suggest $q \mid x$ which impossible as $0 \lt x \lt q$. Thus, we can make the stronger statement that $0 \lt s' \lt q$, which is one of the things we needed to show.
We can push our argument even further, however. Substituting for $s'$, we have $0 \lt px - qy \lt q$. Recalling that $0 \lt x \lt q$, replacing $x$ with $q$ will only make the middle expression bigger, so $0 \lt pq - qy$. Dividing by $q$, we quickly arrive at $y \lt p$. Similarly, replacing $x$ with $0$ only makes that middle expression smaller, so $p \cdot 0 - qy \lt q$, which quickly leads to $-1 \lt y$. Recalling that $y$ must be odd, we can strengthen this to $0 \lt y$. Putting things together, we have $0 \lt y \lt p$.As such, $s' \in S$ implies $s \in T^+$.
Arguing the other direction, suppose $t \in T^+$. We then know there exist odd integers $x$ and $y$ so that $0 \lt t = px - qy \lt q$ with $0 \lt x \lt q$ and $0 \lt y \lt p$. Additionally note that as $t$ is the difference of two odd products, it must be even. Thus $t$ is and even least residue modulo $q$ of the product $px$, where $x$ is odd and $0 \lt x \lt q$.
As such, $t \in S'$.
Thus, $T$ consists of the union of elements in $S'$ and negatives of elements in $S'$, and $|S| + |S'| = |T|$.
It remains to show $|T|$ is even under the right circumstances. To this end, we attempt to pair off each element $t \in T$ with some other $t^* \in T$ in the following way:
Suppose $t \in T$. Then there exist odd integers $x$ and $y$ where $t = px - qy$, with $0 \lt x \lt q$, $0 \lt y \lt p$, and $-p \lt t \lt q$.
Let $x^* = q-1-x$ and $y^* = p-1-y$, and consider $t^* = px^* - qy^*$. First, note that both $x^*$ and $y^*$ must be odd, given their definitions and the fact that $p$, $q$, $x$, and $y$ are all odd. Also note $0 \lt x \lt q$ with $x$ odd implies $0 \lt x^* \lt q$, and $0 \lt y \lt p$ with $y$ odd implies $0 \lt y^* \lt p$.
Then, observe $$\begin{array}{rcl} t^* &=& px^* - q^*\\ &=& p(q-1-x) - q(p-1-y)\\ &=& pq - p - px - qp + q + qy\\ &=& -p + q - (px - qy)\\ &=& -p + q - t \end{array}$$
Recall $-p \lt t \lt q$, so it must be the case that $-q \lt -t \lt p$.
Finally, adding $-p + q$ to each expression as a means to manufacture the $(-p + q - t)$ seen above, we find $$-p + q - q \lt -p + q - t \lt -p + q + p$$ or more simply, $$-p \lt t^* \lt q$$
Thus, we can pair every $t$ in $T$, with some $t^*$ also in $T$.
So the number of elements in $T$ must be even, unless some members $t$ pair with themselves.
However, if any $t = px - qy$ paired with itself, then we would know that $$\begin{array}{rcl} x &=& q - 1 - x\\ y &=& p - 1 - y \end{array}$$ Solving for $x$ and $y$, we have $x = (q-1)/2$ and $y = (p-1)/2$.
This means that there is at most one element of $T$ that pairs with itself, and this exists if and only if both $(p-1)/2$ and $(q-1)/2$ are odd. But this happens only when $p,q \equiv 3\pmod{4}$.
QED.