# Thread: Primes of the form 8n+1, 8n+3

1. ## Primes of the form 8n+1, 8n+3

Show that primes of the form $8n+1, 8n+3$ are of the form $x^2+2y^2$.

(Note : since primes of the form $4n+1$ are of the form $x^2+y^2$, the difficulty of Lagrange's four square theorem is thus reduced to primes of the form $8n-1$.)

2. Alright, so nobody has answered this problem so I'll give my answer.

For $p=8n+1$, both $-1,\ 2$ are quadratic residues; therefore $-2$ is a quadratic residue.

For $p=8n+3$, neither $-1,\ 2$ are quadratic residues; therefore $-2$ is a quadratic residue.

Therefore we can find $n,m \in \mathbb N$ such that $n^2=mp-2$, i.e. $mp=n^2+2=(n+\sqrt{-2})(n-\sqrt{-2})$. Since $\mathbb{Z}[\sqrt{-2}]$ is a unique factorization domain, and since neither factor on the left is divisible by $p$, we deduce that $p$ is not prime in $\mathbb{Z}[\sqrt{-2}]$, and admits a factorization $p=(a+b\sqrt{-2})(c+d\sqrt{-2})$. Taking norms we get $p^2=(a^2+2b^2)(c^2+2d^2)$, so $p=a^2+2b^2=c^2+2d^2$.

3. Nice problem. Was it meant to be a challenge problem though?

4. Originally Posted by Bruno J.
Show that primes of the form $8n+1, 8n+3$ are of the form $x^2+2y^2$.

(Note : since primes of the form $4n+1$ are of the form $x^2+y^2$, the difficulty of Lagrange's four square theorem is thus reduced to primes of the form $8n-1$.)
There is an inequality about congruences that you need to know in order to proof this result. Let $a$ be an integer so that $\gcd(a,p)=1$ where $p$ is an odd prime. Then you can solve the congruence $ax\equiv y(\bmod p)$ with the inequality such that $0<|x|,|y|<\sqrt{p}$.

Let us prove this congruence inequality. Define $n = [\sqrt{p}]+1$ and consider $ax-y$ for $0\leq x,y\leq n-1$. There are $n\cdot n = n^2 >p$ such choices for $x$ and $y$, therefore, $ax_1 - y_1 \equiv ax_2 - y_2(\bmod p)$ for $x_1\not = x_2 \text{ or }y_1\not = y_2$ by pigeonholing modulo $p$. Thus, $a(x_1 - x_2) \equiv (y_1-y_2)(\bmod p)$. Set $x_3=x_1-x_2 \text{ and }y_3=y_1-y_2$. Thus, we get that $ax_3 \equiv y_3(\bmod p)$. It must be the case that $x_3,y_3\not = 0$ because otherwise this would force $x_1=x_2\text{ and }y_1=y_2$ which would be a contradiction. Thus, $|x_3|,|y_3|>0$ but they also satisfy $|x_3|,|y_3| by construction. Thus, we have found a solution for $ax\equiv y(\bmod p)$ which satisfies this inequality.

If $p\equiv 1(\bmod 8)$ then $(-2/p) = (-1/p)(2/p) = (1)(1)=1$ and if $p\equiv 3(\bmod 8)$ then $(-2/p) = (-1/p)(2/p) = (-1)(-1)=1$. Thus, in either case there exists $a\in \mathbb{Z}$ such that $a^2\equiv -2(\bmod p)$. By above there exists a solution to $ax\equiv y(\bmod p)$ with $0<|x|,|y|<\sqrt{p}$. Then, $-2x^2\equiv a^2x^2 = (ax)^2 \equiv y^2 (\bmod p)$. Thus, $2x^2+y^2\equiv 0(\bmod p)$. This means, by definition, there exists $k\geq 1$ such that $2x^2+y^2 = kp$. However, $0 < 2x^2+y^2 < 2(\sqrt{p})^2 + (\sqrt{p})^2 = 3p$. This forces, $k=1,2$. If $k=1$ then $2x^2 + y^2 = p$ and the proof is complete. Otherwise, $2x^2+y^2 = 2p$. But then this forces $y$ to be even, so $y=2z$. This implies $2x^2 + 4z^2 = 2p \implies x^2 + 2z^2 = p$. In either case it is always possible to express $p$ like so.

5. Originally Posted by Jameson
Nice problem. Was it meant to be a challenge problem though?
Yes; sorry I didn't specify, will do in the future.

6. Originally Posted by Bruno J.
Alright, so nobody has answered this problem so I'll give my answer.

For $p=8n+1$, both $-1,\ 2$ are quadratic residues; therefore $-2$ is a quadratic residue.

For $p=8n+3$, neither $-1,\ 2$ are quadratic residues; therefore $-2$ is a quadratic residue.

Therefore we can find $n,m \in \mathbb N$ such that $n^2=mp-2$, i.e. $mp=n^2+2=(n+\sqrt{-2})(n-\sqrt{-2})$. Since $\mathbb{Z}[\sqrt{-2}]$ is a unique factorization domain, and since neither factor on the left is divisible by $p$, we deduce that $p$ is not prime in $\mathbb{Z}[\sqrt{-2}]$, and admits a factorization $p=(a+b\sqrt{-2})(c+d\sqrt{-2})$. Taking norms we get $p^2=(a^2+2b^2)(c^2+2d^2)$, so $p=a^2+2b^2=c^2+2d^2$.
Now argue that $p=a^2+2b^2$ must be unique if $a,b>0$.

7. It follows from the fact that at most two prime ideals can lie over a prime $p\mathbb{Z}$ in a quadratic extension. Since $(a+b\sqrt{-2}),\: (a-b\sqrt{-2})$ are two ideals lying over $p\mathbb{Z}$, there can be no other such ideals. This implies that there can be no other element of norm $p$ : any other such element would generate another principal ideal of norm $p$, which is impossible.

8. Originally Posted by Bruno J.
It follows from the fact that at most two prime ideals can lie over a prime $p\mathbb{Z}$ in a quadratic extension. Since $(a+b\sqrt{-2}),\: (a-b\sqrt{-2})$ are two ideals lying over $p\mathbb{Z}$, there can be no other such ideals. This implies that there can be no other element of norm $p$ : any other such element would generate another principal ideal of norm $p$, which is impossible.
There is just a little bit more work here to be done. First we need to know that $(a+b\sqrt{-2})\not = (a-b\sqrt{-2})$ but this is easy because otherwise $2a \in (a+b\sqrt{-2})$ and so $2a,p\in (a+b\sqrt{-2})$ which will force $(a+b\sqrt{-2}) = \mathbb{Z}[\sqrt{-2}]$ because $(2a,p) = 1$. Also, if $p=x^2+2y^2$ then $(x+y\sqrt{-2})$ is a prime ideal and so $(x+y\sqrt{-2}) = (a+b\sqrt{-2}) \text{ or }(x+y\sqrt{-2}) = (a-b\sqrt{-2})$. Thus, $x+y\sqrt{-2} = \pm (a\pm b\sqrt{-2})$. So it is still possible to generate the same ideals with different elemetns, it is just that these elements differ by only a multiple of unit. Thus, $x=\pm a, y=\pm b$.

I asked the question about uniqueness of expression because I seen lots of people simply say, "uniquness in factorization implies uniquness of expression" but a lot of times this kind of argument is not so easy. I have seen expression problems which do not even have a uniquness up to $\pm 1$, they were more complicated. Usually, if there are are many units then the express is "less unique".