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

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

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

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

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

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

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

Therefore we can find $\displaystyle n,m \in \mathbb N$ such that $\displaystyle n^2=mp-2$, i.e. $\displaystyle mp=n^2+2=(n+\sqrt{-2})(n-\sqrt{-2})$. Since $\displaystyle \mathbb{Z}[\sqrt{-2}]$ is a unique factorization domain, and since neither factor on the left is divisible by $\displaystyle p$, we deduce that $\displaystyle p$ is not prime in $\displaystyle \mathbb{Z}[\sqrt{-2}]$, and admits a factorization $\displaystyle p=(a+b\sqrt{-2})(c+d\sqrt{-2})$. Taking norms we get $\displaystyle p^2=(a^2+2b^2)(c^2+2d^2)$, so $\displaystyle 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 $\displaystyle 8n+1, 8n+3$ are of the form $\displaystyle x^2+2y^2$.

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

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

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

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

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

7. It follows from the fact that at most two prime ideals can lie over a prime $\displaystyle p\mathbb{Z}$ in a quadratic extension. Since $\displaystyle (a+b\sqrt{-2}),\: (a-b\sqrt{-2})$ are two ideals lying over $\displaystyle p\mathbb{Z}$, there can be no other such ideals. This implies that there can be no other element of norm $\displaystyle p$ : any other such element would generate another principal ideal of norm $\displaystyle 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 $\displaystyle p\mathbb{Z}$ in a quadratic extension. Since $\displaystyle (a+b\sqrt{-2}),\: (a-b\sqrt{-2})$ are two ideals lying over $\displaystyle p\mathbb{Z}$, there can be no other such ideals. This implies that there can be no other element of norm $\displaystyle p$ : any other such element would generate another principal ideal of norm $\displaystyle p$, which is impossible.
There is just a little bit more work here to be done. First we need to know that $\displaystyle (a+b\sqrt{-2})\not = (a-b\sqrt{-2})$ but this is easy because otherwise $\displaystyle 2a \in (a+b\sqrt{-2})$ and so $\displaystyle 2a,p\in (a+b\sqrt{-2})$ which will force $\displaystyle (a+b\sqrt{-2}) = \mathbb{Z}[\sqrt{-2}]$ because $\displaystyle (2a,p) = 1$. Also, if $\displaystyle p=x^2+2y^2$ then $\displaystyle (x+y\sqrt{-2})$ is a prime ideal and so $\displaystyle (x+y\sqrt{-2}) = (a+b\sqrt{-2}) \text{ or }(x+y\sqrt{-2}) = (a-b\sqrt{-2})$. Thus, $\displaystyle 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, $\displaystyle 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 $\displaystyle \pm 1$, they were more complicated. Usually, if there are are many units then the express is "less unique".