# How to show $( \frac{p}{q})=1 \Leftrightarrow ( \frac{q}{p})=1$?

How to show $( \frac{p}{q})=1 \Leftrightarrow ( \frac{q}{p})=1$?, where p and q are odd primes and $( \frac{p}{q})$ is Legendre symbol and we assume $q \equiv 1 \pmod 4$. I would like to have proof which uses Euler's criterion if possible. I guess this is possible to solve without quadratic reciprocity.

• What's the context? In particular, do you know quadratic reciprocity? – mrf Jun 7 '13 at 10:52
• mrf: I added supplementary information. – user2723 Jun 7 '13 at 10:56
• The statement is equivalent to quadratic reciprocity, which is proved here [planetmath.org/ProofOfQuadraticReciprocityRule] – Angela Richardson Jun 7 '13 at 12:08
• Link cannot be found. I only found this link which does not contain proof for my problem: planetmath.org/quadraticreciprocityrule – user2723 Jun 7 '13 at 12:28
• @AngelaRichardson: I wouldn't call it equivalent, as it assumes $q\equiv 1\mod 4$. The link is planetmath.org/proofofquadraticreciprocityrule but there should be many more proofs on the web. – darij grinberg Jun 7 '13 at 13:15

Let me give an inductive proof following the argument in the fourth section of Disqusitiones Arithmeticae by Gauß.

Some prerequisites:
I assume known here the Euler criterion, and its consequences, such as the quadratic reciprocity at $-1$.
Also, I divide the situation into some cases, but, in order to make the argument consistent, some orders will be twisted in demonstrating them, so that the orders in enumerating and in demonstrating will differ.
And here the full law is proved.

First, some notations ought to be established: for two integers $a, b$, we write $a Rb$ to denote that $a$ is a residue of $b$, and $a Nb$ conversely.
Then, we use the induction: since $3 N5$ and $5 N3$, the theorem is true up to $5$. Now, if the statement is false, there is $T$ such that the statement is true up to $T$, but to $T+1$ it is false, that is to say, there is a prime $p\le T$ such that $p$ and $a:=T+1$, when compared together, falsify the proposition. There are $8$ ways they can falsify the propoition:

First case: $T+1\equiv p\equiv1\pmod4$, and $p R a$.
Let $p\equiv e^2\pmod a$, where $e$ is even and $<a$, which is possible since $a$ is odd. We distinguish two cases:
I. $p\not|e$ : Let $e^2=p+af$. Then $af\le a^2-p<a^2$, so $f<a$. And $f\equiv-1\pmod4$. Then $p R f$, so, by induction, $f R p$. Also, $(af) R p$, and hence $a R p$.
II. $p\mid e$ : Write $e=pg$ and $e^2=p+aph$ with $h\equiv3\pmod4$, or, $pg^2=1+ah$. Again $h$ is strictly less than $a$. Now, since $pg^2 R h$, by induction, we have $h R p$. Further, $ah\equiv-1\pmod p$, thus $ah R p$. Consequently $a Rp$.
Hence, in the first case, the proposition is true.

Second Case: $T+1\equiv1\pmod4$, and $p\equiv3\pmod4$ and $p R(T+1)$:
As above, let $e^2=p+fa$ with $e$ even and $<a$.
I. $p\not\mid e$ : Completely as above.
II. $p\mid e$ : As above as well.

Third case: $T+1\equiv p\equiv1\pmod4$ and $p N a$.
We take any prime less than $a$ of which $a$ is a non-residue (which fact was established previously during 4 articles; please take this as granted, or see if I can come up with a shorter proof later, or just read the book directly.), i.e. $a N a'.$ We have to treat two cases separately according as the prime $a'$ is $\equiv 1\pmod4$ or $\equiv3\pmod4$.
I. $a'\equiv 1\pmod4$: By induction we have $a' N a$. So $pa' R a$. Now let $e^2\equiv a'p\pmod a$, where $e$ is even and $\lt a$.
And we shall divide into four cases again.
(i) $p\not\mid e$, and $a'\not\mid e$:
Let $e^2=a'p\pm af$, with $f\gt0$. Then $f\lt a$ and $\gcd(f,a')=\gcd(f,p)=1$. For $+$, $f\equiv -1\pmod4$; for $-$, we have $f\equiv1\pmod4$.
Now, we denote, for $x, y\in \mathbb Z$, the number of prime factors of $y$ for which $x$ is a non-residue by $[x,y]$.
If one of $p$ and $a'$, denoted by r, is such that $f N r$, then also $r N f$ by induction. Hence, if $rr'=pa'$, then $r' N f$ as well. Namely, either $f$ is a non-residue of both $p$ and $a'$, or $f$ is a residue of both. So $[f,a'p]=0, 2$.
However, $af R a'$ and $a N a'$ by assumption. Thus $f N a'$. Therefore $[f,a'p]=2$. Hence $f N p$.
Since $af R p$, we then have $a N p$, as desired to prove.
(ii) $p\mid e$, but $a'\not\mid e$:
Let $e=gp$ and $g^2p=a'\pm ah$, with the sign such that $h\gt0$. Then $h\lt a$, and $\gcd(h,a')=\gcd(h,g)=\gcd(h,p)=1$. if the sign is $+$, $h\equiv -1\pmod4$, and $h\equiv1\pmod4$ otherwise. Since $\begin{cases}(gp)^2=pa'\pm pah\\g^2a'p=(a')^2\pm aa'h\end{cases}$, we then deduce $\begin{cases}pa' R h&(\alpha)\\ahp R a'&(\beta)\\aa'h R p&(\gamma)\end{cases}$. Now, by the same reason as used in (i) above, and for $[pa',h]=0$, we find that $[h,pa']$ is either $0$ or $2$.
Suppose $[h,pa']=2$. Then from $(\beta)$ we find that $ap N a'$, so $p R a'$. Thus, by induction, $a' R p$. But from $(\gamma)$ we have $aa' N p$. Therefore $a N p$ again.
Suppose $[h,pa']=0$. Then $(\beta)\implies ap R a'$, and hence $p N a'$, hence $a' N p$. And $(\gamma)\implies aa' R p$, and hence $a N p$ again.
(iii) $a'\mid e$ but $p\not\mid e$:
Arguments almost identical, so that we do not repeat here.
(iv) $p\mid e$ and $a'\mid e$:
We can suppose that $p\not=a'$, otherwise, the assumption would imply that $a N p$. Let now $e=a'pg$ and $g^2a'p=1\pm ah$, with $h\gt0$. Then $h\lt a$ and $\gcd(a',h)=\gcd(p,h)=1$. And $+\implies (h\equiv -1\pmod4)$ and $-\implies (h\equiv 1\pmod4)$. We further deduce $\begin{cases}a'p R h&(\alpha)\\ah R a'&(\beta)\\ah R p&(\gamma)\end{cases}$. By the same trick as used in (ii), we find that $[h,a'p]=0, 2$. If $[h,a'p]=0$, then $(\beta)$ gives $a R a'$, a contradiction. So $h N p$ and, by $(\gamma)$, $a N p$ as well.
II. $a'\equiv-1\pmod4$:
The demonstration is similar to the above one, and it would be futile to repeat here.

Fourth Case: $a\equiv 1\pmod4$, $p\equiv-1\pmod4$, and $p N a$
For the sake of brevity, and since it is very similar to the third case, we omit it here, as Gauss did in the book.

Fifth Case: $a\equiv p\equiv-1\pmod4$, and $p R a$
Let $e^2vequiv p\pmod a$ with $e$ even and $e\lt b$.
I. $p\not\mid a$
Let $e^2=ap+af$, where $f\gt0$, $f\lt a$, $f\equiv-1\pmod4$, and $\gcd(f,p)=1$. Then $p R f$, and so, by induction, $-f R p$. Since $af R p$, we would have $-a R p$, i.e. $a N p$.
II. $p\mid e$
Let $e=pg$, and $g^2p=1+ah$, where $h\equiv1\pmod4$ and $\gcd(h,p)=1$. And $p\equiv g^2p^2\pmod h$, so $p R h$. Now, by induction, we would also have $h R p$. Since $-ah R p$, we find that $-a R p$, or $a N p$.
Sixth Case: $a\equiv-1\pmod4$ and $p\equiv1\pmod4$, and $p N a$.$Since the demonstration is completely like the preceding, we omit the proof here. Seventh Case :$a\equiv p\equiv-1\pmod4$and$p N a$Let$-p\equiv e^2\pmod a$with$e$even and$\lt b$. I.$p\not\mid e$Let$-p=e^2-af$with$f\gt0$,$\gcd(p,f)=1$, and$\lt a$(for$e\le a-1$, and$p\lt a-1$, and so$af=e^2+p\lt (a-1)^2+(a-1)=a(a-1)$. Hence$f\lt a-1$). Further, from$-p R f$we deduce that$f R p$. Since$af R p$, we conclude that$a R p$. II.$p\mid e$Let$e=pg$and$pg^2=-1+ah$where$h\gt0$,$h\equiv-1\pmod4$,$\gcd(h,p)=1$, and$h\lt a$. Now we have$-p R h$, and so$h R p$. Since$ah R p$, it follows that$a R p$. Eighth Case :$a\equiv-1\pmod4$and$p\equiv1\pmod4$and$p N a\$
The demonstration is the same as in the preceding case.

Finally I have completed this answer.
Despite its extreme length, I think it is still of some value. Thanks very much then for reading and paying attention.

• I actually typed in a word document, even though it was unreadable in word, so that I can type smoothly: if I type online, I would be stopped once in ten seconds, because of this length. And please forgive some typos: my computer is almost broken everytime I clicked the bottom "edit". :P – awllower Jul 19 '13 at 14:00