# Legendre Symbol and infinite descent method

Use infinite descent method to prove that for $p$ an odd prime: $$\left(\frac{2}{p}\right)=-1$$ if $$p \equiv\pm 3\pmod 8$$

Please I don't know how to connect two ideas. I'm sure any help would be useful.

Thank you so much :)

You can use the following lemma to prove the statement by an infinite-descent argument, which lemma could be found in Number Theory: An Approach Through History from Hammurapi to Legendre by André Weil, Chap. II. §XII.(See also §VIII.)

First observe that $$(x^2-2y^2)(z^2-2t^2)=(xz\pm2yt)^2-2(xt\pm yz)^2.$$
We call this process the "composition" of two representations of $x^2-2y^2$ and of $z^2-2t^2.$ Namely, the composition of $(x,y)$ and $(z,t)$ is one of the two pairs $(xz\pm 2zt,xt\pm yz).$

Lemma
For any $N=a^2-2b^2,$ let $q=x^2-2y^2$ be a prime divisor of $N.$ Then $N/q=u^2-2v^2$ for some $u, v$ such that $(a,b)$ is obtained by composition from $(u,v)$ and $(x,y).$

Proof
We find $$Nq=(ax\pm2by)^2-2(ay\pm bx)^2,$$
while $q$ divides $$Ny^2-b^2q=(ay)^2-(bx)^2=(ay+bx)(ay-bx),$$
and hence $q$ divides one of $ay\pm bx.$
Thus, with the sign suitably chosen, we see that $q$ also divides $(ax\pm2by).$ With this sign, let $$\begin{cases}ax\pm2by=qu\\ay\pm bx=qv\end{cases}.$$
This shows $N/q=u^2-2v^2.$
Moreover, solving the system of linear equations for $a$ and $b$ proves the lemma.
$\square$

If you cannot figure the descent out, the following is one way.

Let $p$ be a prime divisor of an integer of the form $N=x^2-2y^2$(You may take $y=1$). Then we shall show that $p$ is of that form as well: this shows that $p\not\equiv\pm3\pmod8,$ by congruence considerations. Notice that the set $\{-(p-1)/2,\cdots,(p-1)/2\}$ forms a complete set of residues modulo $p,$ so that we may assume that $x, y\lt p/2,$ hence $N\lt 3p^2/4,$ and therefore every prime divisor of $N$ other than $p$ is strictly less than $p.$ Now we construct the descent: if all primes less than $p$ have a representation, then apply the lemma to a prime divisor $q$ of $N$ other than $p,$ obtain a representation for $N/q,$ and so on, until we reach a representation for $p$ itself, which is a contradiction. So this completes the descent-argument.

Hope this helps.:)

• The essence relating two ideas (quadratic residue and infinite-descent) is the introduction of quadratic forms. – awllower Mar 4 '14 at 17:28