Showing that for any composite binary number $b > 1$, $bb$ is also composite.

72 Views Asked by At

Say $b$ is the binary form of a composite number $d > 1$, I want to prove that $bb$ (concatenation of $b$ with itself) is also a composite number.

My approach:

  • Given a binary number $b$, $bb$ is obtained by a series of transformations picked from $2b, 2b + 1$ (since appending a 0 is equivalent to $2b$ and appending a 1 is equivalent to $2b + 1$)

  • We can rule out all series of transformations whose last transformation is appending a $0$ because these are even numbers

  • Are there any prime numbers of the form $2n + 1, n > 1$? Turns out there is (for $n=3$ and probably more). So that seems like a dead-end.

1

There are 1 best solutions below

2
On BEST ANSWER

If $n$ is the bit-length of $b$, $\overline{bb}=b(2^n+1)$. Since $d>1$, $n\ge2$ and $b>1$. Thus $\overline{bb}$ is composite.