# Prove that a prime $p\equiv 1 \pmod 8$ can be written in the form $x^2+2y^2.$

Prove that a prime $$p\equiv 1\pmod 8$$ can be written in the form $$x^2+2y^2.$$

But it didn't give the solution I require.

We are supposed to use

break up the numbers $$\{1, 2, . . . , p − 1\}$$ into sets of the form $$\{x, \bar{x}, -x, -\bar{x}, ix, −ix, i\bar{x}, −i\bar{x}\}$$, where $$i^2 \equiv −1 \pmod p$$. Then analyze how many elements these sets have.

Here $$\bar{x}$$ mean the inverse of $$x\pmod p$$

So we have $$\{1, 2, . . . , p − 1\}.$$ I didn't get how to incorporate $$i.$$

So here's the analysis for $$\{x, \bar{x}, -x, -\bar{x}\}.$$

• If $$x\equiv \bar{x}\pmod p\implies x^2\equiv 1\pmod p\implies x\equiv 1,p-1.$$

This gives $${1,p-1}$$

• If $$x\equiv -{x}\pmod p\implies 2x\equiv 0\pmod p.$$ Not possible.
• If $$x\equiv -\bar{x}\pmod p\implies x^2\equiv -1\pmod p.$$

Which is possible only when $$p\equiv 1\pmod 4.$$ And this will give only $$x,-\bar{x}$$ to be different. That is $$-x\equiv \bar{x}\pmod p.$$

Now these break elements of $$\{1, 2, . . . , p − 1\}$$ into groups of $$4$$ or $$2$$ ( of $${1,p-1}$$ and sometimes $${x,-\bar{x}}$$)

Now, I did the same thing with $$\{ix, −ix, i\bar{x}, −i\bar{x}\}.$$

• If $$ix\equiv i\bar{x}\pmod p\implies x^2\equiv 1\pmod p\implies x\equiv 1,p-1.$$
• If $$ix\equiv -{x}i\pmod p\implies 2x\equiv 0\pmod p.$$ Not possible.
• If $$ix\equiv -\bar{x}i\pmod p\implies x^2\equiv -1\pmod p.$$ This will give us only $$x,-\bar{x}$$ to be different.

Any hints?

• math.stackexchange.com/questions/1303441/… Commented Aug 12, 2021 at 15:55
• @Yorch it doesn't contain the answer i need.. :( Commented Aug 12, 2021 at 16:41
• it appears you are asking about the first step only, that $-2$ is a quadratic residue mod an odd prime $p$ when $p \equiv 1 \pmod 8;$ still true when $p \equiv 3 \pmod 8$ of course. Some books I have do Gauss lemma and quadratic character of $2$ together. Commented Aug 12, 2021 at 16:44
• Oh yes! Ic how qrs are coming in. Well yes, we can divide by y^2 and get (x/y)^2+2\equiv 0\mod p, which is true only for p, 1,3 mod 8. And we are done. But I want to use the hint, since this method the book had is supposed to use very elementary things. Commented Aug 12, 2021 at 16:52

## 1 Answer

Your analysis is almost there. Take $$p \equiv 1\pmod{8}.$$

Look at $$A =\{x, x^{-1}, -x, -x^{-1}\}.$$ The only possible overlap is if $$x^2 \equiv \pm 1\pmod{p},$$ as you analyzed.

Now, look at $$B=\{ix, ix^{-1}, -ix, -ix^{-1}\}.$$ The only possible overlap is again if $$x^2\equiv \pm 1\pmod{p}.$$

When is $$A \cap B$$ non-empty? Well, if $$x \in A\cap B$$ then we must have $$x \equiv \pm ix^{-1}\pmod{p}$$ or $$x^2 \equiv \pm i\pmod{p}.$$ Similarly, if $$x^{-1}, -x, -x^{-1}$$ belong to $$A\cap B$$ you derive the same conclusion about $$x.$$

So, except for when $$x$$ is either $$1, -1, i, -i,$$ or a square root of $$\pm i,$$ the set $$A\cup B$$ has eight distinct elements. For $$x=1,$$ the set has elements $$\{1, -1, i, -i\},$$ which is four elements. With the zero leftover, this only gives us a number of elements which is 5 mod 8; in particular, since $$p$$ is 1 mod 8, we're missing some elements. Thus, there has to be some $$x$$ so that $$x^2 \equiv \pm i\pmod{p}.$$ Since $$-1$$ is a square mod $$p,$$ $$i$$ has a square root iff $$-i$$ does, so wlog say $$x^2 \equiv i \pmod{8}.$$

Now, in the complex numbers, it's easy to see that a square root of $$i$$ should look like $$\sqrt{2}/2 + \sqrt{-2}/2.$$ This is the motivation for what we do.

Because now that we know $$x^2 \equiv i\pmod{8},$$ to extract a square root of $$2$$ we just consider $$2x/(1+i).$$ Squaring this we get $$4x^2/(1+i)^2 = 4x^2/2i = -2ix^2 = -2ii = 2.$$ Thus, $$2$$ has a square root modulo $$p.$$