Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

More precisely, does there exist a natural number $p$ such that $(2^p-1)/(p+2)$ is also a natural number? It seems to me that this is a really simple problem (with the answer "no"), but I couldn't find anything on the web. There are some facts known about division by $p+1$, but nothing useful for $p+2$.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

Someone should double-check this, but my computer seems to be telling me that $${2^{20735}-1\over20737}{\rm\ and\ }{2^{93525}-1\over93527}$$ are natural numbers. No other examples up to 100001.

It appears that these numbers have been tabulated.

share|improve this answer
    
I think you forgot the $-1$ in the numerator. –  EuYu Aug 30 '12 at 2:58
    
@EuYu, thanks - fixed now. –  Gerry Myerson Aug 30 '12 at 4:41
2  
I can confirm the computations. Also in case nobody noticed $\frac{2^0-1}{0+2}=0$ is a natural number (to me). –  Marc van Leeuwen Aug 30 '12 at 6:49

If $p$ is even, $p+2$ cannot divide $2^p-1$

Else p is odd.

If $(p+2)\mid(2^p-1),$ $2^p≡1\pmod{p+2}$ but $2^{\phi(p+2)}≡1\pmod{p+2}$

So, $\operatorname{ord}_{p+2}2$ must divide $(\phi(p+2),p)$.

If p+2 is prime, $(\phi(p+2),p)=(p+1,p)=1$.

Else $\phi(p+2)<p$ as in that case $\phi(p+2)<p+1$ and $\phi(p+2)≠p$, if $p$ is odd prime $\implies(\phi(p+2),p)=1$

So if at least one of $p$ and $p+2$ is odd prime, $\operatorname{ord}_{p+2}2\mid1$ which is impossible.

When both of them are composite,

If $p+2=\prod Q_i^{r_i}$ where $r_i$s are positive integers and $Q_i$ are distinct odd primes,

As $(p,p+2)=(p,2)=1$ as $p$ is odd,

so, $(p,Q_i)=1 \implies (p, \phi(p+2))= (p, \prod Q_i^{r_i-1}(Q_i-1))=(p, \prod(Q_i-1))$

If $Q_i-1=2^{s_i}q_i$ where $q_i$ is odd number, $(p, \phi(p+2))=(p, \prod(Q_i-1))$ $=(p, \prod q_i)$ as $p$ is odd.

share|improve this answer

Another proof is as follows. First for $p=2$, it follows because $2^p-1=3<4=p+2$. For odd primes $p$, there is a theorem (see Mersenne Prime for proof) that states that every factor of $2^p-1$ is of the form $2kp+1$ for some integer $k\geq0$. Thus we want a $p$ for which $p+2=2kp+1$. There is no such prime because for $p>2$, we have $1<p+2<2p+1$ thus requiring $0<k<1$, a contradiction to the theorem.

share|improve this answer
1  
But OP didn't say $p$ was prime. –  Gerry Myerson Aug 30 '12 at 2:44
    
In fact $p+2=2kp+1 \implies (2k-1)p=1$ –  lab bhattacharjee Aug 30 '12 at 4:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.