1
$\begingroup$

For example, is it so that if we append enough number of $0$s followed by a $1$, any element $x\in \mathbb{Z}_p^*$ can be interpreted as a prime number, where $p$ is a $k$-bit prime for parameter $k$? (e.g. $x0000\ldots 1$)

[update]

What I mean is that the $0$s and $1$ are binary bits. So suppose $p=2^{127}-1$, $x=2^{126} \iff x=\underbrace{1000\ldots00_2}_{126}$. Can we append, say $n$ $0$s and a $1$ such that $x'=x\underbrace{00\ldots0}_{n}1_2=\underbrace{1000\ldots00_2}_{126+n}1$ is a prime?

And can we do so for arbitrary $x\in \mathbb{Z}_p^*$?

[Update]

Let's ignore the $p$ and $k$, they aren't relevant in general. What Chris Culter said is right: can we find prime in the form of $2^nx+1$ for arbitrary $x>0$?

$\endgroup$
  • $\begingroup$ To clarify, can you give a concrete example of what you mean? $\endgroup$ – Chris Culter Apr 25 '18 at 21:24
  • 1
    $\begingroup$ Post-update: It seems like you're asking: for every number $x$, does there exist a prime number of the form $2^mx+1$? I'm not sure how $p$ and $k$ are relevant. $\endgroup$ – Chris Culter Apr 25 '18 at 22:04
2
$\begingroup$

$$ 78557 \cdot 2^n+1 $$ is always composite (as proved by Selfridge via covering congruences). Finding such numbers is an old problem of Sierpinski.

$\endgroup$
1
$\begingroup$

If interpreted as a standard decimal integer, the answer is no, because 2 followed by any number of zeros and then a 1 is divisible by 3.

Similarly, in any base B, the digit B-2 followed by any number of zeros and a 1 is divisible by B-1.

$\endgroup$
  • $\begingroup$ I agree, but I'm more interested in finding either a non-trivial counter-example or proof so I added a restriction that $x>0$ and the base is 2. $\endgroup$ – xtt Apr 25 '18 at 22:15

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.