# Is every Mersenne prime of the form : $x^2+3 \cdot y^2$?

How to prove or disprove following statement :

Conjecture :

Every Mersenne prime number can be uniquely written in the form : $x^2+3 \cdot y^2$ ,

where $\gcd(x,y)=1$ and $x,y \geq 0$

Since $M_p$ is an odd number it follows that : $M_p \equiv 1 \pmod 2$

According to Fermat little theorem we can write :

$2^p \equiv 2 \pmod p \Rightarrow 2^p-1 \equiv 1\pmod p \Rightarrow M_p \equiv 1 \pmod p$

We also know that :

$2 \equiv -1 \pmod 3 \Rightarrow 2^p \equiv (-1)^p \pmod 3 \Rightarrow 2^p-1 \equiv -1-1 \pmod 3 \Rightarrow$

$\Rightarrow M_p \equiv -2 \pmod 3 \Rightarrow M_p \equiv 1 \pmod 3$

So , we have following equivalences :

$M_p \equiv 1 \pmod 2$ , $M_p \equiv 1 \pmod 3$ and $M_p \equiv 1 \pmod p$ , therefore for $p>3$

we can conclude that : $M_p \equiv 1 \pmod {6 \cdot p}$

On the other hand : If $x^2+3\cdot y^2$ is a prime number greater than $5$ then :

$x^2+3\cdot y^2 \equiv 1 \pmod 6$

Proof :

Since $x^2+3\cdot y^2$ is a prime number greater than $3$ it must be of the form $6k+1$ or $6k-1$ .

Let's suppose that $x^2+3\cdot y^2$ is of the form $6k-1$:

$x^2+3\cdot y^2=6k-1 \Rightarrow x^2+3 \cdot y^2+1 =6k \Rightarrow 6 | x^2+3 \cdot y^2+1 \Rightarrow$

$\Rightarrow 6 | x^2+1$ , and $6 | 3 \cdot y^2$

If $6 | x^2+1$ then : $2 | x^2+1$ , and $3 | x^2+1$ , but :

$x^2 \not\equiv -1 \pmod 3 \Rightarrow 3 \nmid x^2+1 \Rightarrow 6 \nmid x^2+1 \Rightarrow 6 \nmid x^2+3 \cdot y^2+1$ , therefore :

$x^2+3\cdot y^2$ is of the form $6k+1$ , so : $x^2+3\cdot y^2 \equiv 1 \pmod 6$

We have shown that : $M_p \equiv 1 \pmod {6 \cdot p}$, for $p>3$ and $x^2+3\cdot y^2 \equiv 1 \pmod 6$ if $x^2+3\cdot y^2$ is a prime number greater than $5$ .

This result is a necessary condition but it seems that I am not much closer to the solution of the conjecture than in the begining of my reasoning ...

-
I understand that the answer given by Andre is good but I've read your arguments and there is one leak when you say that $6 \, | \, x^2 + 3y^2 + 1$ implies that $6 \, | \, x^2 + 1$ and $6 \, | \, 3y^2$ ; unless I missed something, $a \, | \, b+c$ does not imply $a \, | \, b$ and $a \, | \, c$ in general. –  Patrick Da Silva Jan 3 '12 at 16:29
Good point, anyhow that can be fixed, because his argument is based on the fact that $x^2+1$ is not a multiple of $3$. That part of the argument should read: $6 | x^2+3 \cdot y^2+1 \Rightarrow 3 | x^2+1$ which leads to the contradiction... –  N. S. Jan 3 '12 at 16:39
@PatrickDaSilva,@N.S.,In my opinion both of you are right... –  pedja Jan 3 '12 at 16:47
@N.S. I didn't think about it much more, but yes, that could do it. Good point to you too. –  Patrick Da Silva Jan 3 '12 at 17:08

It is a theorem that may have been first proved by Euler (but was known to Fermat) that every prime $p$ of the form $6k+1$ can be expressed in the form $p=x^2+3y^2$, where $x$ and $y$ are integers.

This representability question has been discussed on StackExchange. Please see here for a compact complete proof by Ewan Delanoy.

-
,Happy new year !!! Where can I find proof of that theorem ? Have you any reference ? –  pedja Jan 3 '12 at 16:21
@pedja, see Primes of the Form $x^2+ny^2$, by David Cox. –  lhf Jan 3 '12 at 16:27
@lhf,thanks.... –  pedja Jan 3 '12 at 16:33

(Outline of proof that, for prime $p\equiv 1\pmod 6$, there is one positive solution to $x^2+3y^2=p$.)

It helps to recall the Gaussian integer proof that, for a prime $p\equiv 1\pmod 4$, $x^2+y^2=p$ has an integer solution. It starts with the fact that there is an $a$ such that $a^2+1$ is divisible by $p$, then uses unique factorization in the Gaussian integers to show that there must a common (Gaussian) prime factor of $p$ and $a+i$, and then that $p$ must be the Gaussian norm of that prime factor.

By quadratic reciprocity, we know that if $p\equiv 1\pmod 6$ is prime, then $a^2=-3\pmod p$ has a solution.

This means that $a^2+3$ is divisible by $p$. If we had unique factorization on $\mathbb Z[\sqrt{-3}]$ we'd have our result, since there must be a common prime factor of $p$ and $a+\sqrt{-3}$, and it would have to have norm $p$, and we'd be done.

But we don't have unique factorization in $\mathbb Z[\sqrt{-3}]$, only in the ring, R, of algebraic integers in $\mathbb Q[\sqrt{-3}]$, which are all of the form: $\frac{a+b\sqrt{-3}}2$ where $a=b\pmod 2$.

However, this isn't really a big problem, because for any element $r\in R$, there is a unit $u\in R$ and an element $z\in\mathbb Z[\sqrt{-3}]$ such that $r=uz$.

In particular, then, for any $r\in R$, the norm $N(r)=z_1^2+3z_2^2$ for some integers $z_1,z_2\in \mathbb Z$.

As with the Gaussian proof for $x^2+y^2$, we can then use this to show that there is a solution to $x^2+3y^2=p$. To show uniqueness, you need to use properties of the units in $R$.

-