# 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. Jan 3, 2012 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... Jan 3, 2012 at 16:39
• @PatrickDaSilva,@N.S.,In my opinion both of you are right... Jan 3, 2012 at 16:47
• @N.S. I didn't think about it much more, but yes, that could do it. Good point to you too. Jan 3, 2012 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 ? Jan 3, 2012 at 16:21
• @pedja, see Primes of the Form $x^2+ny^2$, by David Cox.
– lhf
Jan 3, 2012 at 16:27
• @lhf,thanks.... Jan 3, 2012 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$.