# Finding primes for which a given number is a perfect square.

Find all primes p such that $(2^{p-1}-1)/p$ is a perfect square.

I know we can factorise $(2^{p-1}-1)$ into two distinct factors which will be coprime and hence p can divide one of these factors only. How to move further?

-
Welcome to the site. People here don't like questions that are ordering them to do something. To make sure you get more responses you should tell us if this is homework and what you have tried so far. Good luck. – Stijn Jan 31 '12 at 8:30
sorry!, edited :) – Rohan Jan 31 '12 at 8:34

As you noticed, this factors into

$$\frac{2^\ell \pm 1}{p} (2^\ell \mp 1), \text{ where } \ell = \frac{p-1}{2}.$$

Notice that both factors are coprime. If $x=uv$ is a square, with $(u,v)=1$, then you can probably show that $u$ and $v$ must both be squares.

For which $\ell$ is $2^\ell\pm 1$ square? In other words, let's solve. $$2^\ell \pm 1 = u^2.$$ Unless $\ell=0$, the left hand side is odd, so $u=2u'+1$ must be odd. $$2^{\ell} \pm 1 = u^2 = (2u'+1)^2 = 4u'^2 + 4u' + 1,$$

1. Fist assume the sign on the left hand side is $-1$, then we would have that $2^{\ell} -2 = 4u'^2 + 4u'$. Considering this equation mod $4$ severely reduces possibilities: $2^\ell \equiv 2 \pmod 4$ implies $\ell=1$. and indeed $p=3$ is a solution.
2. If the sign is $+1$, on the other hand, this reduces to $$2^{\ell-2} = u' (u'+1),$$ so $u'$ and $u'+1$ are consecutive powers of two, again severely limiting the possibilities: we must have that $u'=1$, i.e $u=3$, i.e. $\ell=3$, i.e. $p=7$. And indeed, $p=7$ is a solution.
-
If case $1$, the addition went awry, you should have the equation $2^{2k}=2{u^'}^2+2{u^'}+1$, and then say "because the right hand side is odd, $k$ must be $0$." – Eric Naslund Jan 31 '12 at 9:50
@Eric: yes, it got a bit messy, I've rewritten it a bit, thank you for noticing! – Myself Jan 31 '12 at 9:56
Thanks a lot. I got p=3,7 as the (only) two solutions – Rohan Jan 31 '12 at 10:19
I just got the same solutions while editting (again) :-) (Even though it seems to be better practice on this website to leave something as a small effort to the reader, that felt so unfinished that I've decided against it and included the solutions anyway.) – Myself Jan 31 '12 at 10:25
Yes, I was looking for a direction and not a solution . I enjoyed the severe reduction and limitations of the possibilities :) – Rohan Jan 31 '12 at 13:08

Note that :

$$\frac{(2^{p-1}-1)}{p}=\frac{(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1)}{p}$$

Let us define $q$ and $r$ as :

$q=2^{\frac{p-1}{2}}+1$ and $r=2^{\frac{p-1}{2}}-1$

Note that : $q=r+2$

Suppose that : $p>2$ and $p \mid q \Rightarrow q=k \cdot p$ for $k \geq 1$

Now let us consider the case when $k>1$ :

$$\frac{q \cdot r}{p}=k \cdot r \Rightarrow k \mid r \Rightarrow r=n\cdot k \Rightarrow k\cdot p=n \cdot k+2 \Rightarrow p=n+\frac{2}{k}$$

which is contradiction since $p$ is a prime number greater than $2$ .

This means that if $p \mid q$ then $p=q$ , similarly one can show that if $p \mid r$ then $p=r$ .

So , we have shown that :

$p=2^{\frac{p-1}{2}}+1$ or $p=2^{\frac{p-1}{2}}-1$

All possible solutions are primes $3,5,7$ since right hand sides of the equalities above are bigger than left hand sides for every prime greater than $7$ .

Simply check gives us solutions : $3$ and $7$ .

-