An equation for prime numbers $\frac{p-1}{2}(2^p-1)+1=7k^2$

170 Views Asked by At

If $2^p-1$ is a Mersenne prime, and $k$ is an integer, then solve $$\frac{p-1}{2}(2^p-1)+1=7k^2$$

$$$$ If I take modulo $p$ I get $1 \equiv 14k^2 \pmod{p}$.

If I take modulo $q=2^p-1$ I get $1 \equiv 7k^2 \pmod{q}$.

Can I use these to solve the equation? Please help me.

1

There are 1 best solutions below

4
On

This is only a partial answer, but I hope it may help a little. Your evaluations modulo $p$ and $q$ are of course correct, but the argument can be carried a little further. You already know that the case $p=3$ is impossible, so I will assume in what follows that $p > 3$.

It is easily verified that $2^p - 1 \equiv 1 \pmod{6p}$. Thus from the original equation one has $\frac{p-1}{2} + 1 \equiv 7k^2 \pmod{6p}$, or multiplying throughout by $2$,

\begin{equation} p + 1 \equiv 14k^2 \pmod{12p}. \end{equation}

Furthermore, the original equation may be written

\begin{equation} \frac{p - 1}{2} \cdot q + 1 = 7k^2, \end{equation}

which when $\frac{p-1}{2}$ is even reduces to

\begin{equation} 1 \equiv 7k^2 \pmod{2q}, \end{equation}

making $k$ odd, while when $\frac{p-1}{2}$ is odd it reduces to

\begin{equation} \frac{p - 1}{2} + 1 \equiv 7k^2 \pmod{2q}, \end{equation}

or, multiplying throughout by 2,

\begin{equation} p + 1 \equiv 14k^2 \pmod{4q}. \end{equation}

Third, we can ask under what conditions the left-hand side of the original equation can be divisible by 7, as required. Simply by brute-force exhaustion of all possible cases, it is found that a necessary and sufficient condition is for $p$ to belong to either of the two residue classes $5, 13 \pmod{42}$. Since there are $\phi(42) = 12$ possible residue classes for primes $\pmod{42}$, this condition eliminates $\frac{5}{6}$ of the primes $p$ from consideration.

Finally, it is easily verified that $2^p - 1 \equiv 31 \pmod{48}$. Thus from the original equation one has $31 \cdot \frac{p-1}{2} + 1 \equiv 7k^2 \pmod{48}$, which being multiplied throughout by $62$ gives

\begin{equation} p + 61 \equiv 50k^2 \pmod{96}. \end{equation}

Taking into account all possible values of $k^2$ modulo $96$, we see that $p$ can only belong to one of the eight residue classes $5, 11, 35, 37, 43, 53, 67, 85 \pmod{96}$. Since there are $\phi(96) = 32$ possible residue classes for primes $\pmod{96}$, this condition eliminates $\frac{3}{4}$ of the primes $p$ from consideration.

EDIT: Taking into account the observation by Erick Wong, the congruence $1 \equiv 7k^2 \pmod{q}$ in the original posting proves that 7 is a quadratic residue of $q$. Because $p \equiv 1 \pmod{6}$ would imply $q \equiv 15 \pmod{28}$, and 7 is a quadratic non-residue of all such primes $q$, this case is impossible and eliminates all instances above where $p \equiv 1 \pmod{6}$. Thus, $p \equiv 5 \pmod{42}$, and $p \equiv 5, 11, 35, \textrm{or } 53 \pmod{96}$.

Similarly, the congruence $1 \equiv 14k^2 \pmod{p}$ in the original posting proves that 14 is a quadratic residue of $p$. This limits $p$ to the residue classes $1, 5, 9, 11, 13, 25, 31, 43, 45, 47, 51, 55 \pmod{56}$, i.e. to 12 of the $\phi(56) = 24$ possible residue classes.