Problem :

Find all natural from the format : $2^{n}-1,n\in \mathbb N^{*}$ they are less then $10^{5}$ and written as product two different $p,q$ prime numbers

My try :

$n=1$ so $1<10^{5}$ $×$

$n=2$ so $3<10^{5}$ but $3≠p.q$ , $p,q=$ prime number $×$

$n=3$ so $7<10^{5}$ but $7≠p.q$ $×$

$n=4$ so $15<10^{5}$ and $15=3.5$ $√$

But I need method to find all this number ??

  • 4
    $\begingroup$ $2^{17}-1>10^5$, so you don't have very many more to check $\endgroup$ – J. W. Tanner Nov 7 at 23:44
  • $\begingroup$ $2^p-1$ with $p\in\{2,3,5,7,13\}$ is (Mersenne) prime $\endgroup$ – J. W. Tanner Nov 7 at 23:53
  • 2
    $\begingroup$ $2^{2k}-1=(2^k-1)(2^k+1)$ $\endgroup$ – J. W. Tanner Nov 7 at 23:54
  • $\begingroup$ @J.W.Tanner what about $n=$ odd $\endgroup$ – Ellen Ellen Nov 8 at 9:20
  • $\begingroup$ I'm sure there are tables of factorizations of Mersenne numbers somewhere on the web. There are also programs to do factorizations. And there's the Online Encyclopedia of Integer Sequences. $\endgroup$ – Gerry Myerson Nov 8 at 11:24

For $n=2k$, $2^n-1=(2^k+1)(2^k-1)$.

Factorizations of $2^n-1$ for $n=2k+1$ can be found in the Cunningham tables.

For $n=2, 3, 5, 7$, or $13$, $2^n-1$ is prime.

With this information, you should be able to answer your question.

  • $\begingroup$ Thank you very much @J.W.Tanner , but if $n=$ odd then how I prove it ?? $\endgroup$ – Ellen Ellen Nov 8 at 18:25
  • $\begingroup$ how you prove what? $\endgroup$ – J. W. Tanner Nov 8 at 18:27
  • $\begingroup$ How I prove $n=$ only odd $\endgroup$ – Ellen Ellen Nov 8 at 21:49
  • $\begingroup$ He never said that. he said that for odd $n$ you can check a table. In general if $n=2^jk$ then it applies his factorization of $2^n-1$ ; $j$ times and has at least $j$ factors. Similar if you found a factorization of $2^n-1$ when it's divisible by 3, etc. $\endgroup$ – Roddy MacPhee Nov 9 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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